Multiplex communications – Wide area network – Packet switching
Patent
1992-01-10
1995-07-18
Black, Thomas G.
Multiplex communications
Wide area network
Packet switching
395800, 370 60, 36422941, 3642319, 36424294, 3649314, 36493141, 36494061, 36494064, 36494067, 36494991, 36494993, 364DIG2, G06F 15173, G06F 15163, G06F 1516
Patent
active
054349729
ABSTRACT:
A large number of processor cells 11, the majority of which are standard cells 12 and others special cells 13, are connected to a communication network 14 in the form of several binary trees. The cells 11 are connected at the leaf positions of the binary trees, and the nodes of the binary trees are formed by switching circuits that allow individual cells to control the formation of signal paths through the nodes. In operation, cells may be in a waiting state, a free state, a calling state, searching state, a communicating state, or an internal operation state. Cells 12 in the free state transmit a free signal into the network 14. Cells 12 or 13 in a searching state transmit a searching signal into the network 14 where, on meeting a free signal at a node, a route is formed from the searching state cell to a free state cell. A calling state cell 12 establishes, with a calling signal, a route through the network 14 to another cell identified by destination information in the calling signal. Cells 11 in the waiting state are waiting to be called by a cell 12 in the calling state. Expressions, in the form of lambda expressions, to be reduced to a final result are so distributed through groups of the cells 11 that only primitive operations and communication need be carried out by the cells 11.
REFERENCES:
patent: 3566362 (1971-02-01), Taylor
patent: 3646523 (1972-02-01), Berkling
patent: 3978452 (1976-08-01), Barton et al.
patent: 4075689 (1978-02-01), Berkling
patent: 4156903 (1979-05-01), Barton et al.
patent: 4156908 (1979-05-01), Missios et al.
patent: 4156910 (1979-05-01), Barton et al.
patent: 4237447 (1980-12-01), Clark
patent: 4251861 (1981-02-01), Mago
patent: 4251879 (1981-02-01), Clark
patent: 4307446 (1981-12-01), Barton et al.
patent: 4344134 (1982-08-01), Barnes
patent: 4412285 (1983-10-01), Neches et al.
patent: 4445171 (1984-04-01), Neches
patent: 4447875 (1984-05-01), Bolton et al.
patent: 4502118 (1985-02-01), Hagenmaier, Jr. et al.
patent: 4583164 (1986-04-01), Tolle
patent: 4591971 (1986-05-01), Darlington et al.
patent: 4598400 (1986-07-01), Hillis
patent: 4638475 (1987-01-01), Koike
patent: 4663708 (1987-05-01), Taub
patent: 4780873 (1988-10-01), Mattheyses
patent: 4814973 (1989-03-01), Hillis
patent: 4814980 (1989-03-01), Peterson et al.
patent: 4831519 (1989-05-01), Morton
patent: 4843540 (1989-06-01), Stolfo
patent: 4858177 (1989-08-01), Smith
patent: 4860201 (1989-08-01), Stolfo et al.
patent: 4908751 (1990-03-01), Smith
patent: 4964032 (1990-10-01), Smith
patent: 5047917 (1991-09-01), Athas et al.
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5168572 (1992-12-01), Perkins
patent: 5175733 (1992-12-01), Nugent
patent: 5181017 (1993-01-01), Frey, Jr. et al.
patent: 5265207 (1993-11-01), Zak et al.
patent: 5276895 (1994-01-01), Grondalski
M. Lease, M. Lively, "Comparing Production System Architectures", Computer Architecture News, vol. 16, No. 4 pp. 108 to 116, published Sep. 1988.
G. Mago, W. Partain "Implementing Dynamic Arrays: A Challenge for High Performance Machines" ICS 87, Second International Conference on Supercomputing. Proceedings, Supercomputing '87. pp. 491 to 493 vol. 1, 1987.
S. Momoi, S. Shimada, M. Kobayashi, T. Ishikawa, "Hierachical Array Processor System (HAP)" CONPAR 86, Conference on Algorithms and Hardware for Parallel Processing Proceedings. pp. 311 to 318, 1986.
J. Seals, G. Grube, "Functional Programming Languages and Modern Multiprocessor Architectures: The EMSP Example" pp. 37-1 to 37-5, Software Engineering and its Application to Avionics. AGARD-CP-439, 1988.
A. Turing, "Proposals for Development in the Mathematics Division of an Automatic Computing Engine (ACE)" National Physical Laboratory, Com Sci 57, Apr. 1972.
W. Hillis, "The Connection Machine", Scientific American, vol. 256, No. 67, 1987, pp. 86 to 93.
Backus, J., "Can Programming Be Liberated From the von Neuann Style? A Functional Style and Its Algebra of Programs," Communications of the ACM, 1978.
K. Berkling, "A Computing Machine Based on Tree Structures," IEEE Transactions on Computers, Apr. 1971.
A. Booth, K. Booth, Automatic Digital Calculators, pp. 22-35. 1956.
Byte, (International Edition), Nov. 1988, "In Depth Parallel Processing".
J. Darlington, M. Reeve, S. Wright, "Declarative Lanugages and Program Transformation for Programming Parrellel Systems: A Case Study," Concurrency: Practice and Experience, vol. 2, Sep. 1990.
R. Duncan, "Evaluating Advanced Architectures for AI Production Systems," IEEE, 1989.
P. Franaszek, "Tree-Based Local Network," IBM Technical Disclosure Bulletin, vol. 25, Apr. 1983.
H. Huskey, "From ACE to the G-15," Annals of the History of Computing, vol. 6, Oct. 1984.
C. Leiserson, "FAT-TREES: Universal Networks for Hardware-Efficient Supercomputing," IEEE, 1985.
G. Mago, "A Network of Microprocessors to Execute Reduction Lanugages, Part I," International Journal of Computer and Information Sciences, vol. 8, 1979.
C. Mago, "A Network of Microprocessors to Execute Reduction Languages, Part II," International Journal of Computer and Information Sciences, vol. 8, No. 6, 1979.
G. Mago, "A Cellular Computer Architecture for Functional Programming," IEEE, 1980.
G. Mago, "Making Parallel Computation Simple: The FFP Machine," IEEE, 1985.
K. Ravikanth, K. Ramakrishnan, Y. Venkatesh, "A Reduction Architecture for the Optimal Scheduling of Binary Trees," Future Generations Computer Systems 4, 1988.
H. Siegel, R. McMillen, "The Multistage Cube: A Versatile Interconnection Network," IEEE, Dec. 1981.
T. Sterling, E. Chan, "A Practical Static Data Flow Computer Based on Associative Methods," Proceedings of the 1988 Intn'l Conf on Parallel Processing, Aug. 1988.
T. Sueyoshi, K. Saisho, I. Arita, "HYPHENC-16--A Prototype of Hierarchical Highly Parallel Processing System," Sep. 1984.
T. Sueyoshi, "Hierarchical Routing Bus," Systems and Computers in Japan, Nov. 1985.
T. Sueyoshi, K. Saisho, "Performance Evaluation of the Binary Tree Access Mechanism in MIMD Type Parallel Computers," Systems and Computers in Japan, vol. 17, 1986.
D. Turner, "A New Implementation Technique for Applicative Languages," Software-Practice and Experience, vol. 9, 1979.
S. Vegdahl, "A Survey of Proposed Architectures for the Execution of Functional Languages," IEEE Transactions on Computers, vol. C-33, No. 12, Dec. 1984.
K. E. Batcher, "Design of a Massively Parallel Processor," IEEE Transactions on Computers, vol. C-29, No. 9, Sep. 1980.
Ellis Horowitz and Alessandro Zorat, "The Binary Tree as an Interconnection Network: Applications to Multiprocessor Systems and VLSI", IEEE, 1981.
Sueyoshi, Toshinori et al., "Hyphen C-16--A Prototype of a Hierarchical Highly Parallel Processing System", J. Data Processing Soc., pp. 1-24, Apr. 1984.
T. Blank, "The MasPar MP-1 Architecture," Proceedings of Compcon Spring 90--The Thirty-Fifth IEEE Computer Society International Conference, Feb. 26-Mar. 2, 1990, pp. 20-24.
J. R. Nickols, "The Design of the MasPar MP-1: A cost Effective Massively Parallel Computer," Proceedings of Compcon Spring 90--The Thirty-Fifth IEEE Computer Society Intn'l conf., Feb. 27-Mar. 2, 1990, pp. 20-24.
P. Christy, "Software to Support Massively Parallel Computing on the MasPar MP-1," Digest of Papers Spring Compcon 1990, Feb. 27-Mar. 1, 1990, pp. 29-33.
Burstall, R. M. et al., Journal of the Association of Computing Machinery, "A Transformation System for Developing Recursive Programs", vol. 24, No. 1, Jan. 1977, pp. 44-67.
Clarke, T. J. W., et al., Proceedings of the LISP Conference, "SKIM--The S,K,I, Reduction Machine", Stanford, 1980, pp. 128-135.
Darlington, John, et al., Proceedings of ACM/MIT Conference on Functional Languages and Computer Architecture, "Alice: A Multiprocessor Reduction Machine for the Parallel Evaluation of Applicative Languages", 1981, pp. 65-75.
Davis, A. L., Proceedings of 1979 National Computer Conference, "A data flow evaluation system based on the concept of recursive locality", AFIPS Press, Jun. 4-7, 1979, pp. 1079-1086.
Landin, P. J., The Computer Journal, "The mechanical evaluation of expressions", vol. 6, Apr. 1963 to Jan. 1964, pp. 3
Black Thomas G.
GEC--Marconi Limited
Harrity Paul
LandOfFree
Network for determining route through nodes by directing searchi does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network for determining route through nodes by directing searchi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network for determining route through nodes by directing searchi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2421859