Patent US3119005A successfully refreshed from Google Patents.
EP0472879A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and apparatus for dynamic detection and routing of non-uniform traffic in parallel buffered multistage interconnection networks
Assignee: International Business Machines Corp
•
Filing: 1991-07-16
•
Granted: —
•
Expires: 2011-07-16
Abstract
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.
Inventors
- 👤 Suresh Chalasani
- 👤 Anujan Managla Varma
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 08:02
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17393
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
127 words
Apparatus for routing 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; feedback means for notifying said plurality of processing elements as to the 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, one suited to uniform traffic conditions and the other suited to non-uniform traffic conditions.
Claim 2
Dependent Claim
90 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in claim 1 wherein said means for selecting comprises: a memory-status table addressed by a memory address from said processing element, 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; and packet router means responsive to said select output for routing a memory request from said processing element to one of said switching networks.
Claim 3
Dependent Claim
57 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in claim 2 wherein said means for selecting further includes means for preventing memory requests from a corresponding one of said processing elements from getting out of order due to said requests being routed through different ones of said at least two switching networks.
Claim 4
Dependent Claim
128 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in claim 3 wherein said means for preventing memory requests from getting out of order comprises: an outstanding-request table addressed by said memory address from said processing element, said outstanding-request table providing a first output indicating whether an addressed memory module has been previously addressed but no response has been received from that memory module and a second output identifying the switching network over which the previous request was routed; and comparing means in said selector circuit enabled by said first output of said outstanding-request table for comparing said second output with a switching network selected to determine if there is a match and, if so, generating a hold packet output to said processing element.
Claim 5
Dependent Claim
45 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in claim 2, 3 or 4 wherein said means for selecting further comprises counter means responsive to said feedback means for maintaining a count of memory modules having a non-uniform traffic status.
Claim 6
Dependent Claim
57 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in claim 1 or one of the claims 2 to 5 wherein said means for detection of traffic non-uniformities includes detecting means in each of said memory modules for designating the memory module as hot or cool based on monitoring traffic to the module.
Claim 7
Dependent Claim
82 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system as recited in claim 6 wherein said detection means comprises: windowing means for counting the number of requests to the memory module during a predetermined number of cycles; comparing means connected to said windowing means for comparing a count in said windowing means to first and second predetermined thresholds; and flag means set by said count exceeding said first threshold and reset by said count going below said second threshold.
Claim 8
Dependent Claim
35 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system as recited in claim 7 wherein said first and second predetermined thresholds are set by an operating system of said multiprocessor computer system.
Claim 9
Dependent Claim
37 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system as recited in claim 7 or 8 wherein said windowing means is programmable to change the number of cycles during which memory requests are counted.
Claim 10
Dependent Claim
83 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system as recited in claim 1 or anyone of claims 2 to 9 wherein said interconnection system includes a response network for routing response data from said memory modules to said processing elements and said feedback means includes packet formatter means at each of said modules connected to said response network and receiving said response data and responsive to said flag means for inserting a flag indicating traffic non-uniformities at the module.
Claim 11
Independent Claim
117 words
The apparatus for routing processor-memory traffic in a shared-memory multiprocessor computer system recited in anyone of claims 6 to 10 wherein said means within each processing element further comprises a packet deformatter providing as a first output an address of a responding memory module and as a second output the status of the responding memory module and wherein said means for selecting further comprises counter means responsive to said second output of said deformatter for maintaining a count of memory modules having a non-uniform traffic status, said first and second outputs being supplied to said memory-status table for updating the memory-status table and said first output being supplied to said outstanding-request table for updating the outstanding-request table.
Claim 12
Independent Claim
107 words
A method for routing 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 interconnected by at least two multistage switching networks, said method comprising the steps of: dynamically detecting traffic non-uniformities in each memory module; notifying said plurality of processing elements as to a status of each memory module, said status indicating uniform or non-uniform traffic to each memory module; and selecting one of said at least two networks for routing a request based on two different routing methods, one suited to uniform traffic conditions and the other suited to non-uniform traffic conditions.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.