Pipeline system and method for multiprocessor applications in which each of a plurality of threads execute all steps of a process characterized by normal and parallel steps on a respective datum
First Claim
1. A pipeline method for executing a process on a multiprocessor computer system having a plurality of processors and a memory, wherein said process includes a plurality of steps, each of said steps being classified as a normal step or a parallel step, said method comprising the steps of:
- receiving a data stream including a plurality of datums;
executing a plurality of threads on said plurality of processors, each of said threads executing all of said plurality of steps on a respective one of said datums;
said executing step including executing each of said normal steps by at most one of said threads at a time;
said executing step further including executing each of said parallel steps by any number of said threads at a time;
said executing step including constraining said threads to execute said normal steps in the same order that said threads begin execution of said process on successively received ones of said datums.
2 Assignments
0 Petitions
Accused Products
Abstract
A pipelined process execution control system for multiprocessors is disclosed that enables multiple processors to cooperatively execute one or many software processes so that cache locality is not violated and extensive state, or context, information need not be saved and restored for each small piece of work performed on multiple data items. The present pipelined process execution control system incorporates (1) a software procedure defined as a pipelined sequence of normal or parallel steps, (2) multiple threads running on the multiprocessor, each of which executes the entire sequence of steps on one datum or data item from a received data stream, and (3) a process control structure to control the threads executing the sequence of steps, so that the normal steps are executed by only one thread at a time and the threads begin executing (or "enter") subsequent normal steps in the sequence in the same order as the threads entered the first step of the sequence. Parallel steps can be executed by more than one thread in parallel. The process control structure provides a process control data structure to track which of the steps is currently being executed by each thread. To eliminate the possibility of simultaneous memory access attempts by the multiple processors hosting the threads, the process control data structure is accessible to only one thread at a time. One specific process control structure disclosed is a mutex combined with a mutex control data structure.
67 Citations
29 Claims
-
1. A pipeline method for executing a process on a multiprocessor computer system having a plurality of processors and a memory, wherein said process includes a plurality of steps, each of said steps being classified as a normal step or a parallel step, said method comprising the steps of:
-
receiving a data stream including a plurality of datums; executing a plurality of threads on said plurality of processors, each of said threads executing all of said plurality of steps on a respective one of said datums; said executing step including executing each of said normal steps by at most one of said threads at a time; said executing step further including executing each of said parallel steps by any number of said threads at a time; said executing step including constraining said threads to execute said normal steps in the same order that said threads begin execution of said process on successively received ones of said datums. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. In a microprocessor having a plurality of processors and a memory, a pipelined, process execution control system that controls execution of a procedure having a sequence of steps for processing a received data stream having a plurality of datums, each of said steps being classified as one of a normal step or a parallel step, said process execution control system comprising:
-
a thread loader that loads said plurality of processors with a plurality of threads, each of said threads executing all of said steps of said procedure on a respective one of said datums; and a thread controller that coordinates said threads executing said procedure so that said threads execute said normal steps in the same order that said threads execute the first step of said sequence of steps and no more than one of said threads executes one of said single steps at a time. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A computer-readable memory that can be used to direct a microprocessor having a plurality of processors to control execution of a procedure having a sequence of steps for processing a received data stream having a plurality of datums, each of said steps being classified as one of a normal step or a parallel step, said computer-readable memory comprising:
-
a thread loader that loads said plurality of processors with a plurality of threads, each of said threads executing all of said steps of said procedure on a respective one of said datums; and a thread controller that coordinates said threads executing said procedure so that said threads execute said normal steps in the same order that said threads execute the first step of said sequence of steps and no more than one of said threads executes one of said single steps at a time. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29)
-
Specification