System for arbitrating communication requests using multi-pass control unit based on availability of system resources

In a multi-processor system having a system control unit (SCU) for operating a plurality of processors in a parallel fashion, wherein each of said processors is ported into the SCU, the SCU being operative to controllably allow said processors to access addressed segments of a system memory, a method of controlling communication through said SCU in response to communication requests received at the SCU ports from said processors in an efficient and fair manner, each of said requests having a corresponding command that needs to be executed in order to honor said each of said requests by reserving a data transmission path through said SCU, said method comprising the steps of:

• (a) storing in an electronic memory the incoming requests;
• (b) selecting, on the basis of a predefined prioritizing scheme, requests to be arbitrated;
• (c) extracting the command corresponding to each request selected to be arbitrated;
• (d) generating a first vector defining all system resources required for executing the extracted command;
• (e) generating a second vector representative of all system resources that are presently available for executing said extracted command;
• (f) comparing said first and second vectors;
• and
• (1) when said comparing indicates that all of said system resources required for executing said extracted command are presently available, honoring said selected request by executing said extracted command to reserve a data transmission path through said SCU and initiate data transmission over said path;
• and
• (2) when said comparing does not indicate that all of said system resources required for executing said extracted command are presently available, then
• (i) placing the request corresponding to said extracted command on `reserved` status,
• (ii) reserving said system resources required for executing said extracted command, and
• (iii) when all of said system resources required for executing said extracted command corresponding to the reserved request become available, honoring said reserved request by executing said extracted command to reserve a data transmission path through said SCU end initiate data transmission over said path,
• wherein said method further includes:
• a first arbitration pass (the "reserve pass") during which all SCU ports are polled and requests outstanding at the time are arbitrated by honoring requests for which all required system resources are available and placing on reserved status all requests for which all required system resources are not available,
• a second arbitration pass (the "recheck" pass) during which only reserved requests are arbitrated by honoring those reserved requests for which all required system resources have become available at the time and reserving all required system resources for those reserved requests for which all required system resources are not available at the time, and
• a third arbitration pass (the "non-reserve" pass) during which only those requests received at the SCU following the previous "reserve" pass (the "new" requests) are arbitrated by honoring those new requests for which all required system resources are available.

A computer system comprising, in combination:

• (a) a plurality of system units;
• (b) a plurality of system resources for satisfying service requests from said system units, each of a plurality of said service requests requiring the simultaneous availability of more than one of said system resources to perform processes required for satisfying said each of a plurality of said service requests;
• (a) storing means coupled to said system units for storing the service requests from said system units for performing said processes;
• (b) selecting means coupled to said storing means for selecting one of the stored service requests for arbitration;
• (c) resource checking means coupled to said selecting means for determining whether or not all system resources required for performing all processes required for satisfying the selected one of said service requests are presently available;
• (d) process initiating means coupled to said resource checking means for initiating all processes required for satisfying the selected one of said service requests when said resource checking means determines that all system resources required for performing all processes required for satisfying said selected one of said service requests are presently available;
• (e) resource reserving means coupled to said resource checking means for reserving system resources required for performing processes required for satisfying said selected one of said service requests when said resource checking means determines that all system resources required for performing all processes required for satisfying said selected one of said service requests are not presently available, said reserved resources being made unavailable to subsequent requests and not being used for satisfying said selected one of said service requests until all system resources required for performing all processes required for satisfying said selected one of said service requests become available.
• wherein said selecting means includes:
• request reserving means coupled to said resource checking means for placing on reserved status service requests that were not satisfied due to unavailability of required system resources as determined by said resource checking means;
• re-check pass means coupled to said storage means for selecting only service requests stored in said storage means that were placed on reserve status by said request reserving means;
• and
• non-reserve pass means operative after said re-check pass means for selecting only service requests stored in said storage means that have not been placed on reserve status by said request reserving means.