Multicomputer system and method
AssigneeTemple University of the Commonwealth System of Higher Education
InventorYuan Shi
Life of this patent
Estimating the term…
Abstract
A multicomputer system and method for automatic sequential-to-parallel program partition, scheduling and execution. The plurality of computer are connected via a uni-directional slotted ring (backbone). The ring supports, with deterministic delays, point-to-point, broadcast and EXCLUSIVE-READ operations over labeled tuples. The execution of parallel programs uses a connectionless computing method that forms customized coarse grain SIMD, MIMD and pipelined processors automatically using the connected multicomputers. The disclosed multicomputer architecture is also resilient to processor and backbone failures.
Claims53
A stateless machine (SLM) multicomputer system comprising:
- a unidirectional slotted ring;
- a plurality of computers, each computer connected to said unidirectional slotted ring, each computer having a local real memory and an operating system supporting a virtual memory and multiprogramming, with at least one of said plurality of computers, responsive to receiving from said unidirectional slotted ring an initial set of data tuples, for initiating a plurality of program segments, and for transmitting the initial set of data tuples onto said unidirectional slotted ring;
- wherein each data tuple corresponding to initiating a sequential action includes an EXCLUSIVE-READ signal for informing said plurality of computers to cease contending for the data tuple after reading of the data tuple by one of said plurality of computers;
- wherein said plurality of computers, responsive to receiving data tuples, activate the plurality of program segments for processing the received data tuples to produce new processed data tuples;
- and
- wherein said plurality of computers transmit the new processed data tuples onto said unidirectional slotted ring, with sequential acting tuples accompanied by corresponding EXCLUSIVE-READ signals.
A method of messaging without specified destinations using a stateless machine (SLM) multicomputer system using a plurality of computers, each of said plurality of computers having a memory, comprising the steps of:
- sending a plurality of data tuples along a unidirectional slotted ring;
- reading, by an available computer of said plurality of computers, an initial data tuple of a program segment into memory;
- transmitting, from the available computer, in response to receiving from said unidirectional slotted ring the initial data tuple of the program segment, onto said unidirectional slotted ring an EXCLUSIVE-READ signal for informing said plurality of computers of reception of the initial data tuple of the program segment;
- and
- ceasing by said plurality of computers, in response to receiving the EXCLUSIVE-READ signal, contending for data tuples corresponding to the program segment.
A method of messaging without specified destinations using a stateless machine (SLM) multicomputer system using a plurality of computers, each of said plurality of computers having a memory, comprising the steps of:
- sending a plurality of data tuples along a unidirectional slotted ring;
- reading, by an available computer of said plurality of computers, an initial data tuple of a subset of a partitioned program into memory;
- transmitting, from the available computer, in response to receiving from said unidirectional slotted ring the initial data tuple of the subset of the partitioned program, onto said unidirectional slotted ring an EXCLUSIVE-READ signal for informing said plurality of computers of reception of the initial data tuple of the subset of the partitioned program;
- and
- ceasing by said plurality of computers, in response to receiving the EXCLUSIVE-READ signal, contending for data tuples corresponding to the subset of the partitioned program.
A method using a stateless machine (SLM) multicomputer system using a plurality of computers connected to a unidirectional slotted ring, of processing an application program having a plurality of program segments, comprising the steps of:
- sending the plurality of program segments, each of said plurality of program segments labeled according to data dependencies and connected to other program segments by a corresponding plurality of labeled data tuples, along the unidirectional slotted ring;
- loading the plurality of program segments into each computer of said plurality of computers;
- circulating the plurality of labeled data tuples through said plurality of computers;
- receiving, by at least one of said plurality of computers, a matching set of data tuples;
- activating a program segment corresponding to the matching set of data tuples;
- processing the activated program segment;
- transmitting, on the unidirectional slotted ring, a processed result as new labeled sequential acting data tuples, with each new labeled sequential acting data tuple accompanied by an EXCLUSIVE-READ signal;
- and
- processing, by said plurality of computers, the new labeled sequential acting data tuples.
A method for parallel processing using a stateless machine (SLM) multicomputer system having a plurality of computers connected to a unidirectional slotted ring, each of said plurality of computers having a local real memory, comprising the steps of:
- sending a plurality of data tuples along the unidirectional slotted ring;
- detecting an initial data tuple of a program segment by any one of the plurality of computers;
- reading the initial data tuple into a local real memory of the detecting computer;
- transmitting, from the detecting computer, in response to reading from said unidirectional slotted ring the initial data tuple of the program segment, onto said unidirectional slotted ring an EXCLUSIVE-READ signal for informing said plurality of computers of reception of the initial data tuple of the program segment;
- ceasing by said plurality of computers, in response to receiving the EXCLUSIVE-READ signal, contending for data tuples corresponding to the program segment;
- activating the program segment for processing the initial data tuple, using the local real memory, to produce a new processed data tuple;
- and
- sending the new processed data tuple along the unidirectional slotted ring.
A method for messaging without destination using a stateless machine (SLM) multicomputer system having a plurality of computers comprising the steps of:
- sending a plurality of data tuples along a unidirectional slotted ring;
- reading the plurality of data tuples by said plurality of computers;
- transmitting, from one of said plurality of computers, in response to receiving from said unidirectional slotted ring an initial data tuple of a subset of a partitioned program, onto said unidirectional slotted ring an EXCLUSIVE-READ signal for informing said plurality of computers of reception of the initial data tuple of the subset of the partitioned program;
- ceasing by said plurality of computers, in response to receiving the EXCLUSIVE-READ signal, contending for data tuples corresponding to the subset of the partitioned program;
- processing, by said plurality of computers, the plurality of data tuples to produce new data tuples;
- and
- sending the plurality of new data tuples along the unidirectional slotted ring.
Dependencies are inferred from the claim text.