X-Tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

X-Tree: A tree structured multi-processor computer architecture

Full text

Pdf (536 KB)

Source

International Symposium on Computer Architecture archive
Proceedings of the 5th annual symposium on Computer architecture table of contents

Pages: 144 - 151

Year of Publication: 1978

Authors

Alvin M. Despain
David A. Patterson

Sponsors

ACM: Association for Computing Machinery
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 75, Citation Count: 52

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800094.803041 What is a DOI?

ABSTRACT

The problem of organizing multiple, monolithic microprocessors into an effective general purpose computer structure is examined. A tree structure with extra interconnections was found to be especially attractive. It provides a structured hierarchy for control, addressing and message routing. More important, it appears to provide a mechanism to automatically migrate data abstractions and processes over the network of processors. The network can be expanded to any desired size and no global control or routine mechanisms are needed. The potential advantages and disadvantages of the X-Tree structure are discussed and the results of some static simulations are presented.

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	George A. Anderson , E. Douglas Jensen, Computer Interconnection Structures: Taxonomy, Characteristics, and Examples, ACM Computing Surveys (CSUR), v.7 n.4, p.197-213, Dec. 1975 [doi>10.1145/356654.356658]
	2	Richard J. Goodwin, "A design for distributed-control multiple-processor computer systems", National Technical Information Service, AD-772 883, December 1973.
	3	N. Wirth, Towards a discipline of real-time programming, Proceedings of an ACM conference on Language design for reliable software, p.142, March 28-30, 1977, Raleigh, North Carolina
	4	Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973 [doi>10.1145/356622.356624]
	5	William A. Wulf and C.G. Bell, "C.mmp - A Multimini-processor", Fall joint Computer Conference, pp. 765-777, 1972.
	6	R.J. Swan, S.H. Fuller and D.P. Siewiorek, "Cm* - A modular, multi-microprocessor", 1977 National Computer Conference Proceedings, pp. 637-663, June 1977.
	7	Harold S. Stone, "Parallel Processing with the Perfect Shuffle", IEEE Trans. Comput., Vol. C-20, No. 2, pp. 153-161, February 1971.
	8	Robert N. Noyce, "Microelectronics", Scientific American, Vol. 237, No. 3, pp. 62-69, September 1977.
	9	John F. Wakerly, "Reliability of microcomputer systems using triple modular redundancy", Proceedings of Spring COMPCON76, pp. 23-26, February 1976.

CITED BY 52

	Robert H. Kuhn, Efficient mapping of algorithms to single-stage interconnections, Proceedings of the 7th annual symposium on Computer Architecture, p.182-189, May 06-08, 1980, La Baule, United States
	Laxmi N. Bhuyan , Dharma P. Agrawal, A general class of processor interconnection strategies, ACM SIGARCH Computer Architecture News, v.10 n.3, p.90-98, April 1982
	Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States
	Adit D. Singh , Hee Yong Youn, A Modular Fault-Tolerant Binary Tree Architecture with Short Links, IEEE Transactions on Computers, v.40 n.7, p.882-890, July 1991
	Larry D. Wittie , Andre M. van Tilborg, An introduction to network computers, Proceedings of the ACM '82 conference, p.199-206, January 1982
	J. Ghosh , K. Hwang, Critical issues in mapping neural networks on message-passing multicomputers, ACM SIGARCH Computer Architecture News, v.16 n.2, p.3-11, May 1988
	J. G. Kuhl , S. M. Reddy, Distributed fault-tolerance for large multiprocessor systems, Proceedings of the 7th annual symposium on Computer Architecture, p.23-30, May 06-08, 1980, La Baule, United States
	Sandeep N. Bhatt , Fan R. K. Chung , Jia-Wei Hong , F. Thomson Leighton , Bojana Obrenic , Arnold L. Rosenberg , Eric J. Schwabe, Optimal emulations by butterfly-like networks, Journal of the ACM (JACM), v.43 n.2, p.293-330, March 1996
	Roger K. Shultz , Roy J. Zingg, Response Time Analysis of Multiprocessor Computers for Database Support, ACM Transactions on Database Systems (TODS), v.9 n.1, p.100-132, March 1984
	David A. Patterson , E. Scott Fehr , Carlo H. Séquin, Design considerations for the VLSI processor of X-TREE, Proceedings of the 6th annual symposium on Computer architecture, p.90-101, April 23-25, 1979
	Roy Jenevein , Doug Degroot , G. Jack Lipovski, A hardware support mechanism for scheduling resources in a parallel machine environment, Proceedings of the 8th annual symposium on Computer Architecture, p.57-65, May 12-14, 1981, Minneapolis, Minnesota, United States
	Rod Egan, The effect of VLSI on computer architecture, ACM SIGARCH Computer Architecture News, v.10 n.5, p.19-22, September 1982
	Henry Fuchs , Brian W. Johnson, An expandable multiprocessor architecture for video graphics (Preliminary Report), Proceedings of the 6th annual symposium on Computer architecture, p.58-67, April 23-25, 1979
	Hancu , K. C. Smith, DVPP: a VLSI dynamic-graph ensemble machine, Proceedings of the 2nd international conference on Supercomputing, p.90-100, June 1988, St. Malo, France
	Marvin H. Solomon , Raphael A. Finkel, The Roscoe distributed operating system, Proceedings of the seventh ACM symposium on Operating systems principles, p.108-114, December 10-12, 1979, Pacific Grove, California, United States
	C. H. Séquin , A. M. Despain , D. A. Patterson, Communication In X-TREE, A Modular Multiprocessor System, Proceedings of the 1978 annual conference, p.194-203, December 04-06, 1978, Washington, D.C., United States
	Bruce W. Arden , Ran Ginosar, MP/C: A multiprocessor/computer architecture, Proceedings of the 8th annual symposium on Computer Architecture, p.3-19, May 12-14, 1981, Minneapolis, Minnesota, United States
	C.-T. Ho , S. L. Johnsson, Dilation d embedding of a hyper-pyramid into a hypercube, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.294-303, November 12-17, 1989, Reno, Nevada, United States
	Y. C. Hong , T. H. Payne , L. B O Ferguson, Graph allocation in static dataflow systems, ACM SIGARCH Computer Architecture News, v.14 n.2, p.55-64, June 1986
	Hyoung Jhang, Performance of join on an n-dimensional mesh, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.197-203, April 1992, Kansas City, Missouri, United States
	Philip C. Treleaven , Richard P. Hopkins, A recursive computer architecture for VLSI, ACM SIGARCH Computer Architecture News, v.10 n.3, p.229-238, April 1982
	Carlo H. Sequin, Doubly twisted torus networks for VLSI processor arrays, Proceedings of the 8th annual symposium on Computer Architecture, p.471-480, May 12-14, 1981, Minneapolis, Minnesota, United States
	Hyoung Jhang, Performance comparison of join on hypercube and mesh, Proceedings of the 1992 ACM annual conference on Communications, p.243-250, March 03-05, 1992, Kansas City, Missouri, United States
	Lars Philipson , Bo Nilsson , Bjorn Breidegard, A communication structure for a multiprocessor computer with distributed global memory, ACM SIGARCH Computer Architecture News, v.11 n.3, p.334-340, June 1983
	Benjamin W. Wah , Y. W. Ma, MANIP-a parallel computer system for implementing branch and bound algorithms, Proceedings of the 8th annual symposium on Computer Architecture, p.239-262, May 12-14, 1981, Minneapolis, Minnesota, United States
	Fadi N. Sibai, Distributed routing in the recursive diamond network, Proceedings of the 1997 ACM symposium on Applied computing, p.389-392, April 1997, San Jose, California, United States
	Kjell Bratbergsengen , Rune Larsen , Oddvar Risnes , Terje Aandalen, A neighbor connected processor network for performing relational algebra operations, ACM SIGIR Forum, v.15 n.2, p.96-105, March 1980
	Peter K. K. Loh , W. J. Hsu , Amos Omondi, Embedding of fault-tolerant trees in the Josephus Cube, Australian Computer Science Communications, v.24 n.3, p.17-27, January-February 2002
	Dorota M. Huizinga , Ewa Kubicko, A tree generating algorithm for designing optimal hierarchical distributed systems, Proceedings of the 1997 ACM symposium on Applied computing, p.345-353, April 1997, San Jose, California, United States
	Daniel A. Reed, Queueing network models of multimicrocomputer networks, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.190-197, August 29-31, 1983, Minneapolis, Minnesota, United States
	Nian-Feng Tzeng, A Cost-Effective Combining Structure for Large-Scale Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.41 n.11, p.1420-1429, November 1992
	Ronald I. Greenberg, The Fat-Pyramid and Universal Parallel Computation Independent of Wire Delay, IEEE Transactions on Computers, v.43 n.12, p.1358-1364, December 1994
	D. A. Carlson, Modified-Mesh Connected Parallel Computers, IEEE Transactions on Computers, v.37 n.10, p.1315-1321, October 1988
	Shantanu Dutt , J. P. Hayes, On Designing and Reconfiguring k-Fault-Tolerant Tree Architectures, IEEE Transactions on Computers, v.39 n.4, p.490-503, April 1990
	Sivarama P. Dandamudi , D. L. Eager, Hierarchical Interconnection Networks for Multicomputer Systems, IEEE Transactions on Computers, v.39 n.6, p.786-797, June 1990
	Bernard L. Menezes , Roy Jenevein, The KYKLOS Multicomputer Network: Interconnection Strategies, Properties, and Applications, IEEE Transactions on Computers, v.40 n.6, p.693-705, June 1991
	John Tartar, Multiprocessor hardware: An architectural overview, Proceedings of the ACM 1980 annual conference, p.518-526, January 1980
	A. Ghafoor , T. R. Bashkow , I. Ghafoor, Bisectional Fault-Tolerant Communication Architecture for Supercomputer Systems, IEEE Transactions on Computers, v.38 n.10, p.1425-1446, October 1989
	Z. Guo , R. G. Melhem, Embedding Binary X-Trees and Pyramids in Processor Arrays with Spanning Buses, IEEE Transactions on Parallel and Distributed Systems, v.5 n.6, p.664-672, June 1994
	Vipul Gupta , Eugen Schenfeld, Annealed Embeddings of Communication Patterns in an Interconnection Cached Network, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1153-1167, November 1995
	D. B. Skillicorn, A New Class of Fault-Tolerant Static Interconnection Networks, IEEE Transactions on Computers, v.37 n.11, p.1468-1470, November 1988
	James Newsome , Dawn Song, GEM: graph eMbedding for routing and data-centric storage in sensor networks without geographic information, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	J. Tyszer, A Multiple Fault-Tolerant Processor Network Architecture for Pipeline Computing, IEEE Transactions on Computers, v.37 n.11, p.1414-1418, November 1988
	H. Y. Youn , A. D. Singh, On Implementing Large Binary Tree Architectures in VLSI and WSI, IEEE Transactions on Computers, v.38 n.4, p.526-537, April 1989
	Sampalli Srinivas , Nripendra N. Biswas, Design and Analysis of a Generalized Architecture for Reconfigurable m-ary Tree Structures, IEEE Transactions on Computers, v.41 n.11, p.1465-1478, November 1992
	Nripendra N. Biswas , S. Srinivas, A Reconfigurable Tree Architecture with Multistage Interconnection Network, IEEE Transactions on Computers, v.39 n.12, p.1481-1485, December 1990
	Haran Boral , David J. DeWitt, Design considerations for data-flow database machines, Proceedings of the 1980 ACM SIGMOD international conference on Management of data, May 14-16, 1980, Santa Monica, California
	André M. Van Tilborg , Larry D. Wittie, Distributed task force scheduling in multi-microcomputer networks, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois
	Sigurd L. Lillevik , John L. Easterday, A multiprocessor with replicated shared memory, Proceedings of the May 16-19, 1983, national computer conference, May 16-19, 1983, Anaheim, California
	John O'Donnell, Supporting tasks with adaptive groups in data parallel programming, International Journal of Computational Science and Engineering, v.1 n.2-4, p.86-98, May 2005
	Svetlana P. Kartashev , Steven I. Kartashev, Reconfigurable fault-tolerant multicomputer network, Proceedings of the May 16-19, 1983, national computer conference, May 16-19, 1983, Anaheim, California
	Benjamin W. Wah , Y. W. Ma, The architecture of MANIP: a parallel computer system for solving NP-complete problems, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois