WaveScalar

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

WaveScalar

Full text

Pdf (229 KB)

Source

International Symposium on Microarchitecture archive
Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture table of contents

Page: 291

Year of Publication: 2003

ISBN:0-7695-2043-X

Authors

Steven Swanson	Computer Science and Engineering, University of Washington
Ken Michelson	Computer Science and Engineering, University of Washington
Andrew Schwerin	Computer Science and Engineering, University of Washington
Mark Oskin	Computer Science and Engineering, University of Washington

Sponsor

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 28, Citation Count: 34

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Silicon technology will continue to provide an exponential increasein the availability of raw transistors. Effectively translatingthis resource into application performance, however,is an open challenge. Ever increasing wire-delay relativeto switching speed and the exponential cost of circuit complexitymake simply scaling up existing processor designs futile.In this paper, we present an alternative to superscalardesign, WaveScalar. WaveScalar is a dataflow instructionset architecture and execution model designed for scalable,low-complexity/high-performance processors. WaveScalar isunique among dataflow architectures in efficiently providingtraditional memory semantics. At last, a dataflow machinecan run "real-world" programs, written in any language,without sacrificing parallelism.The WaveScalar ISA is designed to run on an intelligentmemory system. Each instruction in a WaveScalar binary executesin place in the memory system and explicitly communicateswith its dependents in dataflow fashion. WaveScalararchitectures cache instructions and the values they operateon in a WaveCache, a simple grid of "alu-in-cache" nodes.By co-locating computation and data in physical space, theWaveCache minimizes long wire, high-latency communication.This paper introduces the WaveScalar instruction setand evaluates a simulated implementation based on currenttechnology. Results for the SPEC and Mediabench applicationsdemonstrate that the WaveCache out-performs an aggressivelyconfigured superscalar design by 2-7 times, withample opportunities for future optimizations.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
	2	Todd M. Austin, DIVA: a reliable substrate for deep submicron microarchitecture design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.196-207, November 16-18, 1999, Haifa, Israel
	3	Ramadass Nagarajan , Karthikeyan Sankaralingam , Doug Burger , Stephen W. Keckler, A design space evaluation of grid processor architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
	4	Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
	5	Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
	6	Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
	7	A. H. Veen, The misconstrued semicolon: reconciling imperative languages and dataflow machines, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1986
	8	[8] S. Allan and A. Oldehoeft, "A flow analysis procedure for the translation of high-level languages to a data flow language," IEEE Transactions on Computers, vol. 29, no. 9, 1980.
	9	Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Doug Burger , Stephen W. Keckler , Charles R. Moore, Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
	10	Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
	11	Warren A. Hunt, Jr., Introduction: Special Issue on Microprocessor Verifications, Formal Methods in System Design, v.20 n.2, p.135-137, March 2002 [doi>10.1023/A:1014175712530]
	12	[12] L. Gwennap, "Digital 21264 sets new standard," Microprocessor Report, vol. 10, October 1996.
	13	[13] "Map-ca datasheet," June 2001. Equator Technologies.
	14	[14] H. Sharangpani, "Intel Itanium processor core," in Hot-Chips, 2000.
	15	Ho-Seop Kim , James E. Smith, An instruction set and microarchitecture for instruction level distributed processing, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
	16	Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
	17	Paramjit S. Oberoi , Gurindar S. Sohi, Parallelism in the front-end, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
	18	Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
	19	David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
	20	M. Kumar, Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications, IEEE Transactions on Computers, v.37 n.9, p.1088-1098, September 1988 [doi>10.1109/12.2259]
	21	Alexandru Nicolau , Joseph A. Fisher, Using an oracle to measure potential parallelism in single instruction stream programs, Proceedings of the 14th annual workshop on Microprogramming, p.171-182, December 01-01, 1981, Chatham, Massachusetts, United States
	22	A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
	23	S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
	24	T. Shimada , K. Hiraki , K. Nishida , S. Sekiguchi, Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations, Proceedings of the 13th annual international symposium on Computer architecture, p.226-234, June 02-05, 1986, Tokyo, Japan
	25	J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
	26	Masasuke Kishi , Hiroshi Yasuhara , Yasusuke Kawamura, DDDP-a Distributed Data Driven Processor, Proceedings of the 10th annual international symposium on Computer architecture, p.236-242, June 13-17, 1983, Stockholm, Sweden
	27	V. G. Grafe , G. S. Davidson , J. E. Hoch , V. P. Holmes, The Epsilon dataflow processor, Proceedings of the 16th annual international symposium on Computer architecture, p.36-45, April 1989, Jerusalem, Israel
	28	Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
	29	David E. Culler , Klaus E. Schauser , Thorsten von Eicken, Two Fundamental Limits on Dataflow Multiprocessing, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.153-164, January 20-22, 1993
	30	[30] R. Nikhil, "The parallel programming language Id and its compilation for parallel machines," in Workshop on Mazzive Paralleism: Hardware, Programming and Applications, 1990.
	31	K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
	32	[32] J. T. Feo, P. J. Miller, and S. K. Skedzielewski, "Sisal90," in High Performance Functional Computing, 1995.
	33	[33] S. Murer and R. Marti, "The FOOL programming language: Integrating single-assignment and object-oriented paradigms," in European Workshop on Parallel Computing, 1992.
	34	[34] J. B. Dennis, "First version data flow procedure language," Tech. Rep. MAC TM61, MIT Laboratory for Computer Science, 1991.
	35	E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
	36	James R. McGraw, The VAL Language: Description and Analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.44-82, Jan. 1982 [doi>10.1145/357153.357157]
	37	[37] J. B. Dennis, "Dataflow supercomputers," in IEEE Computer, vol. 13, 1980.
	38	Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
	39	David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
	40	Seth Copen Goldstein , Mihai Budiu, NanoFabrics: spatial computing using molecular electronics, Proceedings of the 28th annual international symposium on Computer architecture, p.178-191, June 30-July 04, 2001, Göteborg, Sweden
	41	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	42	Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
	43	S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
	44	Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
	45	Manoj Franklin , Gurindar S. Sohi, ARB: A Hardware Mechanism for Dynamic Reordering of Memory References, IEEE Transactions on Computers, v.45 n.5, p.552-571, May 1996 [doi>10.1109/12.509907]
	46	[46] S. Swanson, K. Michelson, and M. Oskin, "Configuration by combustion: Online simulated annealing for dynamic hard-ware configuration," in ASPLOS X Wild and Crazy Idea Session , 2002.
	47	M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
	48	[48] S. McFarling, "Combining Branch Predictors," Tech. Rep. TN- 36, Digital Equipment Corperation, June 1993.
	49	[49] SPEC, "Spec CPU 2000 benchmark specifications." SPEC2000 Benchmark Release, 2000.
	50	Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	51	William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
	52	[52] "Personal communication with doug burger and steve keckler," 2002-2003.
	53	D. E. Culler , Arvind, Resource requirements of dataflow programs, Proceedings of the 15th Annual International Symposium on Computer architecture, p.141-150, May 30-June 02, 1988, Honolulu, Hawaii, United States
	54	Steven Swanson , Luke K. McDowell , Michael M. Swift , Susan J. Eggers , Henry M. Levy, An evaluation of speculative instruction execution on simultaneous multithreaded processors, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.314-340, August 2003 [doi>10.1145/859716.859720]

CITED BY 34

	Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Nitya Ranganathan , Doug Burger , Stephen W. Keckler , Robert G. McDonald , Charles R. Moore, TRIPS: A polymorphous architecture for exploiting ILP, TLP, and DLP, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.1, p.62-93, March 2004
	Michael Bedford Taylor , Walter Lee , Saman P. Amarasinghe , Anant Agarwal, Scalar Operand Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.145-162, February 2005
	Rajagopalan Desikan , Simha Sethumadhavan , Doug Burger , Stephen W. Keckler, Scalable selective re-execution for EDGE architectures, ACM SIGPLAN Notices, v.39 n.11, November 2004
	Youngsoo Kim , Suleyman Sair, Designing real-time H.264 decoders with dataflow architectures, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
	Mongkol Ekpanyapong , Michael Healy , Sung Kyu Lim, Placement for configurable dataflow architecture, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Enric Gibert , Jesus Sanchez , Antonio Gonzalez, Distributed Data Cache Designs for Clustered VLIW Processors, IEEE Transactions on Computers, v.54 n.10, p.1227-1241, October 2005
	Julia Chen , Philo Juang , Kevin Ko , Gilberto Contreras , David Penry , Ram Rangan , Adam Stoler , Li-Shiuan Peh , Margaret Martonosi, Hardware-modulated parallelism in chip multiprocessors, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005
	Joäo M. P. Cardoso, Dynamic loop pipelining in data-driven architectures, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
	Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Modeling instruction placement on a spatial architecture, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Ramadass Nagarajan , Sundeep K. Kushwaha , Doug Burger , Kathryn S. McKinley , Calvin Lin , Stephen W. Keckler, Static Placement, Dynamic Issue (SPDI) Scheduling for EDGE Architectures, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.74-84, September 29-October 03, 2004
	Anne Bracy , Prashant Prahlad , Amir Roth, Dataflow Mini-Graphs: Amplifying Superscalar Capacity and Bandwidth, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.18-29, December 04-08, 2004, Portland, Oregon
	Mahim Mishra , Timothy J. Callahan , Tiberiu Chelcea , Girish Venkataramani , Seth C. Goldstein , Mihai Budiu, Tartan: evaluating spatial computation for whole program execution, ACM SIGOPS Operating Systems Review, v.40 n.5, December 2006
	Katherine E. Coons , Xia Chen , Doug Burger , Kathryn S. McKinley , Sundeep K. Kushwaha, A spatial path scheduling algorithm for EDGE architectures, ACM SIGPLAN Notices, v.41 n.11, November 2006
	Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Instruction scheduling for a tiled dataflow architecture, ACM SIGOPS Operating Systems Review, v.40 n.5, December 2006
	Lin Tan , Brett Brotherton , Timothy Sherwood, Bit-split string-matching engines for intrusion detection and prevention, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.1, p.3-34, March 2006
	Shigeru Kusakabe , Mitsuhiro Aono , Masaaki Izumi , Satoshi Amamiya , Yoshinari Nomura , Hideo Taniguchi , Makoto Amamiya, Scalability of continuation-based fine-grained multithreading in handling multiple I/O requests on FUCE, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy
	Steven Swanson , Andrew Schwerin , Martha Mercaldi , Andrew Petersen , Andrew Putnam , Ken Michelson , Mark Oskin , Susan J. Eggers, The WaveScalar architecture, ACM Transactions on Computer Systems (TOCS), v.25 n.2, p.4-es, May 2007
	Jeffrey R. Diamond , Behnam Robatmili , Stephen W. Keckler , Robert van de Geijn , Kazushige Goto , Doug Burger, High performance dense linear algebra on a spatially distributed processor, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Andrew Petersen , Andrew Putnam , Martha Mercaldi , Andrew Schwerin , Susan Eggers , Steve Swanson , Mark Oskin, Reducing control overhead in dataflow architectures, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA
	Mark Oskin, The revolution inside the box, Communications of the ACM, v.51 n.7, July 2008
	David Wentzlaff , Anant Agarwal, Constructing Virtual Architectures on a Tiled Processor, Proceedings of the International Symposium on Code Generation and Optimization, p.173-184, March 26-29, 2006
	Aaron Smith , Jon Gibson , Bertrand Maher , Nick Nethercote , Bill Yoder , Doug Burger , Kathryn S. McKinle , Jim Burrill, Compiling for EDGE Architectures, Proceedings of the International Symposium on Code Generation and Optimization, p.185-195, March 26-29, 2006
	Steven Swanson , Andrew Putnam , Martha Mercaldi , Ken Michelson , Andrew Petersen , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Area-Performance Trade-offs in Tiled Dataflow Architectures, ACM SIGARCH Computer Architecture News, v.34 n.2, p.314-326, May 2006
	Pierre Palatin , Yves Lhuillier , Olivier Temam, CAPSULE: Hardware-Assisted Parallel Execution of Component-Based Programs, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.247-258, December 09-13, 2006
	Karthikeyan Sankaralingam , Ramadass Nagarajan , Robert McDonald , Rajagopalan Desikan , Saurabh Drolia , M. S. Govindan , Paul Gratz , Divya Gulati , Heather Hanson , Changkyu Kim , Haiming Liu , Nitya Ranganathan , Simha Sethumadhavan , Sadia Sharif , Premkishore Shivakumar , Stephen W. Keckler , Doug Burger, Distributed Microarchitectural Protocols in the TRIPS Prototype Processor, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.480-491, December 09-13, 2006
	Aaron Smith , Ramadass Nagarajan , Karthikeyan Sankaralingam , Robert McDonald , Doug Burger , Stephen W. Keckler , Kathryn S. McKinley, Dataflow Predication, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.89-102, December 09-13, 2006
	Lin Tan , Timothy Sherwood, A High Throughput String Matching Architecture for Intrusion Detection and Prevention, ACM SIGARCH Computer Architecture News, v.33 n.2, p.112-122, May 2005
	Daeho Seo , Akif Ali , Won-Taek Lim , Nauman Rafique , Mithuna Thottethodi, Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks, ACM SIGARCH Computer Architecture News, v.33 n.2, p.432-443, May 2005
	Franziska Roesner , Doug Burger , Stephen W. Keckler, Counting Dependence Predictors, ACM SIGARCH Computer Architecture News, v.36 n.3, p.215-226, June 2008
	Antonio Carlos S. Beck , Mateus B. Rutzig , Georgi Gaydadjiev , Luigi Carro, Transparent reconfigurable acceleration for heterogeneous embedded applications, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Behnam Robatmili , Katherine E. Coons , Doug Burger , Kathryn S. McKinley, Strategies for mapping dataflow blocks to distributed hardware, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.23-34, November 08-12, 2008
	Samuel Rodrigo , Jose Flich , Jose Duato , Mark Hummel, Efficient unicast and multicast support for CMPs, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.364-375, November 08-12, 2008
	Lorenzo De Carli , Yi Pan , Amit Kumar , Cristian Estan , Karthikeyan Sankaralingam, PLUG: flexible lookup modules for rapid deployment of new protocols in high-speed routers, ACM SIGCOMM Computer Communication Review, v.39 n.4, October 2009
	Costas Kyriacou , Paraskevas Evripidou , Pedro Trancoso, Data-Driven Multithreading Using Conventional Microprocessors, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1176-1188, October 2006