Method and apparatus for real-time multithreading
A computer architecture, hardware modules, and a software method, collectively referred to as “EVISA,” are described that allow low-overhead multithreading program execution to be performed in such a way as to keep all processors usefully busy and satisfy real-time timing constraints. The architecture can be incorporated into the design of a multithreading instruction processor, or can be used as a separate architectural module in conjunction with pre-existing non-multithreading processors as well as specialized Intellectual Property (IP) core modules for embedded applications.
1 . A real-time multithreading apparatus, comprising:
one or more multithreading nodes connected by an interconnection network, each multithreading node comprising:
an execution unit for executing active fibers;
a synchronization unit for scheduling and synchronizing fibers and procedures, and handling remote accesses, the synchronization unit interconnecting with the interconnection network; and
a ready queue and an event queue through which the execution unit and the synchronization unit communicate.
2 . A real-time multithreading apparatus as recited in claim 1 , wherein the execution unit has at least one computer processor interconnected with a memory bus.
3 . A real-time multithreading apparatus as recited in claim 2 , wherein the ready queue provides information received from the synchronization unit to the at least one computer processor of the execution unit.
4 . A real-time multithreading apparatus as recited in claim 2 , wherein the event queue provides information received from the at least one computer processor of the execution unit to the synchronization unit.
5 . A real-time multithreading apparatus as recited in claim 1 , further comprising a memory interconnected with and shared by the execution unit and the synchronization unit.
6 . A real-time multithreading apparatus as recited in claim 1 , wherein if a fiber running on the execution unit needs to perform an operation relating to other fibers, the execution unit sends a request to the event queue for processing by the synchronization unit.
7 . A real-time multithreading apparatus as recited in claim 1 , wherein the synchronization unit manages fibers and places any fiber ready for execution in the ready queue.
8 . A real-time multithreading apparatus as recited in claim 1 , wherein the synchronization unit comprises:
a system bus interface through which the execution unit accesses the event queue and the ready queue, and through which the synchronization unit accesses a memory; and
a network interface through which the synchronization unit interconnects with the interconnection network.
9 . A real-time multithreading apparatus as recited in claim 8 , wherein the synchronization unit further comprises:
an internal event queue containing uncompleted events waiting to be finished or forwarded to another node;
an internal ready queue containing a list of fibers ready to be executed; and
a frame identifier/instruction pointer section storing information relevant to each fiber currently being executed by the execution unit.
10 . A real-time multithreading apparatus as recited in claim 9 , wherein the synchronization unit further comprises:
an outgoing message queue buffering messages waiting to go out over the interconnection network;
a token queue holding all pending threaded procedure invocations that have not been assigned to a node; and
an internal cache holding recently-accessed sync slots and data read by the synchronization unit.
11 . A real-time multithreading apparatus as recited in claim 10 , wherein the synchronization unit further comprises:
an execution unit message assembly area collecting sequences of stores from the system bus interface and injecting completed events in the event queue;
a network message assembly area receiving incoming messages and injecting completed messages into the event queue; and
a distributed real-time manager ensuring that events, messages, and fibers with high priority or real-time constraints are placed ahead of objects with lesser priority.
12 . A real-time multithreading method, comprising:
providing one or more multithreading nodes connected by an interconnection network, each multithreading node performing a method comprising:
executing active fibers with an execution unit;
scheduling and synchronizing fibers and procedures, and handling remote accesses with a synchronization unit interconnected with the interconnection network; and
providing communication between the execution unit and the synchronization unit with a ready queue and an event queue.
13 . A real-time multithreading method as recited in claim 12 , wherein the execution unit has at least one computer processor interconnected with a memory bus.
14 . A real-time multithreading method as recited in claim 13 , wherein the providing communication substep includes providing information received from the synchronization unit to the at least one computer processor of the execution unit with the ready queue.
15 . A real-time multithreading method as recited in claim 13 , wherein the providing communication substep includes providing information received from the at least one computer processor of the execution unit to the synchronization unit with the event queue.
16 . A real-time multithreading method as recited in claim 12 , wherein each multithreading node performs a method further comprising interconnecting a memory with the execution unit and the synchronization unit.
17 . A real-time multithreading method as recited in claim 12 , wherein the scheduling and synchronizing fibers and procedures substep includes sending a request to the event queue for processing by the synchronization unit by the execution unit if a fiber running on the execution unit needs to perform an operation relating to other fibers.
18 . A real-time multithreading method as recited in claim 12 , wherein the scheduling and synchronizing fibers and procedures substep includes managing fibers and placing any fiber ready for execution in the ready queue with the synchronization unit.
19 . A real-time multithreading method as recited in claim 1 , wherein the scheduling and synchronizing fibers and procedures substep comprises:
providing a system bus interface through which the execution unit accesses the event queue and the ready queue, and through which the synchronization unit accesses a memory; and
providing a network interface through which the synchronization unit interconnects with the interconnection network.
20 . A real-time multithreading method as recited in claim 19 , wherein the scheduling and synchronizing fibers and procedures substep further comprises:
providing an internal event queue that contains uncompleted events waiting to be finished or forwarded to another node;
providing an internal ready queue that contains a list of fibers ready to be executed; and
providing a frame identifier/instruction pointer section that stores information relevant to each fiber currently being executed by the execution unit.
21 . A real-time multithreading method as recited in claim 20 , wherein the scheduling and synchronizing fibers and procedures substep further comprises:
providing an outgoing message queue that buffers messages waiting to go out over the interconnection network;
providing a token queue that holds all pending threaded procedure invocations that have not been assigned to a node; and
providing an internal cache that holds recently-accessed sync slots and data read by the synchronization unit.
22 . A real-time multithreading method as recited in claim 21 , wherein the scheduling and synchronizing fibers and procedures substep further comprises:
providing an execution unit message assembly area that collects sequences of stores from the system bus interface and injects completed events in the event queue;
providing a network message assembly area that receives incoming messages and injects completed messages into the event queue; and
providing a distributed real-time manager that ensures events, messages, and fibers with high priority or real-time constraints are placed ahead of objects with lesser priority.