Method and apparatus for dynamic detection and routing of non-uniform traffic in parallel buffered multistage interconnection networks
First Claim
1. Apparatus for mounting processor-memory traffic in a shared-memory multiprocessor computer system of the type comprising a plurality of processing elements and a plurality of memory modules, comprising:
- an interconnection system having at least two multistage switching networks, said at least two multistage switching networks each interconnecting said plurality of processing elements and said plurality of memory modules;
means for detecting traffic non-uniformities in each memory module, said detecting means counting a number of requests to a memory module during a predetermined number of cycles and comparing a count to first and second predetermined thresholds; and
feedback means to notifying said plurality of processing elements as to a status of each memory module; and
means within each processing element responsive to said feedback means for selecting one of said at least two networks for routing a request based on two different routing methods, a first of said routing methods suited to uniform traffic conditions and a second of said routing methods suited to non-uniform traffic conditions, said means for selecting comprising;
a memory-status table addressed by a memory address from one of said processing elements, said memory-status table providing a first output indicating a status of an addressed memory module;
a selector circuit responsive to said first output of said memory-status table and generating a select output;
packet router means responsive to said select output for routing a memory request from said one of said processing elements to one of said switching networks; and
counter means responsive to said feedback means for maintaining a count of memory modules having a non-uniform traffic status.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for routing processor-memory data traffic in a shared-memory multiprocessor computer system employs an interconnection network including two buffered multistage switching networks. Each of these networks can be used to route the data from any processing element to any memory element. Depending on the nature of the processor-memory traffic, two distinct routing schemes are used to distribute the traffic among the two networks. The first method distributes the memory accesses evenly among the two networks and maximizes performance when the memory accesses are uniformly distributed among the memory modules. However, when the traffic is highly non-uniform, a second routing method is used to confine the non-uniform part of the traffic to one network and the remaining part to the other network. The routing method is selected based on the prevailing traffic conditions. A distributed feedback mechanism detects the change in traffic conditions and changes the routing method accordingly. A traffic monitoring circuit within each memory module monitors the traffic into the memory module continuously and senses a change in the traffic condition. The condition is conveyed to the processing elements by means of a status flag associated with each response message from the memory module to processing elements. The processing elements respond to a change in traffic condition by switching to the alternate routing method.
-
Citations
12 Claims
-
1. Apparatus for mounting processor-memory traffic in a shared-memory multiprocessor computer system of the type comprising a plurality of processing elements and a plurality of memory modules, comprising:
-
an interconnection system having at least two multistage switching networks, said at least two multistage switching networks each interconnecting said plurality of processing elements and said plurality of memory modules; means for detecting traffic non-uniformities in each memory module, said detecting means counting a number of requests to a memory module during a predetermined number of cycles and comparing a count to first and second predetermined thresholds; and feedback means to notifying said plurality of processing elements as to a status of each memory module; and means within each processing element responsive to said feedback means for selecting one of said at least two networks for routing a request based on two different routing methods, a first of said routing methods suited to uniform traffic conditions and a second of said routing methods suited to non-uniform traffic conditions, said means for selecting comprising; a memory-status table addressed by a memory address from one of said processing elements, said memory-status table providing a first output indicating a status of an addressed memory module; a selector circuit responsive to said first output of said memory-status table and generating a select output; packet router means responsive to said select output for routing a memory request from said one of said processing elements to one of said switching networks; and counter means responsive to said feedback means for maintaining a count of memory modules having a non-uniform traffic status. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
Specification