Method and apparatus for communicating data between a host and a plurality of parallel processors
AssigneeInternational Business Machines Corporation
InventorsDaniel J. Auerbach, Tien C. Chen, Wolfgang J. Paul
Life of this patent
Estimating the term…
Abstract
In a centrally controlled resource arbitration system, each of the units concurrently requesting access sends its identity code and the binary complement thereof to a central arbitration processor. The identity codes are logically combined into a first word, and the binary complements are logically combined into a second word. A subset identifier of the requesting units is then formed by combining corresponding bits of the first and second words. Unresolved values in the subset identifier are iteratively removed to eliminate a subset of the requesting units. When all but one of the requesting units have been eliminated, access to the resource is given to the remaining unit.
Claims15
A method for communicating data between a plurality of individually identifiable processors in a data processing system, comprising the steps, at the processor initiating the communication, of:
- (a) forming a first word by logically combining the identifiers of a subset of processors with which communication is to be established;
- and
- (b) forming a second word which, when combined with said first word in a predetermined manner, designates the subset of processors with which communication is to be established, wherein said second word is formed by, at each bit position:
- (i) generating a bit which has a first state which is the same as a bit of like significance in said first word which, in combination with the bit of like significance in said first word, indicates no bit information in the bit position;
- (ii) generating a bit which has a state opposite that of a bit of like significance in said first word which, in combination with the bit of like significance in the first word, indicates the same bit information as the bit of like significance in said first word;
- and
- (iii) generating a bit which has a second state which is the same as a bit of like significance in said first word which, in combination with the bit of like significance in the first word, indicates either said first state or said second state in said bit position;
- (iv) transmitting said first and second words to a central arbitration processor.
A method for communicating data between a plurality of individually identifiable processors in a data processing system, comprising the steps, at the processor initiating the communication, of:
- (a) forming a first word by logically combining the identifiers of a subset of processors with which communication is to be established;
- (b) forming a second word which, when combined with said first word in a predetermined manner, designates the subset of processors with which communication is to be established;
- and
- (c) combining said first word and said second word to generate a third word by, at each bit position:
- (i) using the state of the bit with like bit significance in said first word if there is a mismatch between the bit of like significance in said first word and the bit of like significance in said second word;
- and
- (ii) using a "don't care" state if there is a match between the bit of like significance in said first word and the bit of like significance in said second word;
- (d) transmitting said third word to said processors to which communication is to be established.
A method for selecting one of N.ltoreq.2.sup.m processors concurrently requesting access to a shared resource through a central processor, each processor being designated by a unique identifier, comprising the steps of:
- (a) forming a first m-bit word and a second m-bit word by logically combining said N identifiers and logically combining N binary complements of the said N identifiers;
- (b) designating a subset of the requesting processors through formation of an m-bit subset identifier by substituting in each bit position thereof a value selected from the set consisting of a first value, a second value, and an ambiguous term, said substitution being governed according to the match and mismatch condition among pairs of bits of the first and second words of like bit significance, the maximum subset size being a function of the position and occurrence of the ambiguous term in the subset identifier;
- and
- (c) eliminating all but one of the designated subsets of requesting processors and then granting access to the remaining processor, according to a dynamically changeable algorithm.
A method for centrally arbitrating access to a shared resource among a set of uniquely identified requesting units, comprising, at each requesting unit, transmitting an m-bit identity code and its binary complement to a central arbitration processor, and, comprising, at the central arbitration processor, the steps of:
- (a) in the event of only one request, granting access to the requesting unit immediately;
- and
- (b) in the event of N.ltoreq.2.sup.m concurrent requests;
- (1) logically combining the N identity codes to form a first m-bit word;
- (2) logically combining the N binary complements of the N identity codes to form a second m-bit word;
- (3) designating a subset of requesting units through formation of a third m-digit position word by translating the combined binary states of each i.sup.th bit of said first m-bit word and the corresponding i.sup.th bit of said second m-bit word into a value in a predetermined manner, and assigning said value to each corresponding i.sup.th bit position of said third m-digit position word;
- and
- (4) eliminating all but one of the units from said designated subset of requesting units according to a dynamically changeable algorithm, and then repeating steps (1), (2), and (3) above.
In a system for arbitrating access to a shared resource among a plurality of uniquely identifiable units, wherein said arbitration is centrally controlled by a central arbitration processor connected to said shared resource and to said plurality of units, a method by which the central arbitration processor addresses a selected subset of said units, comprising the steps of:
- (a) generating an m-bit address by logically combining, at each bit position, corresponding bits of the identity codes of the units of said subset of units;
- (b) generating an m-bit logical complement of said first address based upon a predefined set of protocols;
- and
- (c) generating an m-bit group identifier of said selected subset of units, by translating the combined binary states of each i.sup.th bit of said address and the corresponding i.sup.th bit of said complement into a value in a predetermined manner, and assigning said value to the i.sup.th bit position of said group identifier, wherein said translation is dependent on whether a first bit matches a second bit in one binary state, said first bit matches said second bit in the other binary state, said first bit mismatches said second bit in one direction, or said first bit mismatches said second bit in the other direction;
- (d) excluding from access to said shared resource units whose identity code does not match said m-bit group identifier.
In a system for arbitrating concurrent requests for access to a shared resource among a plurality of uniquely identifiable units, wherein said arbitration is centrally controlled by a central arbitration processor which is connected to the requesting units, an apparatus for unbiasedly communicating access requests to the central arbitration processor, comprising:
- (a) a sender in each requesting unit for sending an m-bit identity code and the m-bit binary complement thereof;
- (b) a first receiver in said central arbitration processor for receiving the identity codes from the requesting units and logically combining, at each bit position, corresponding bits of said identity codes received into a first m-bit word;
- (c) a second receiver in said central arbitration processor for receiving the binary complements of said identity codes from the requesting units and logically combining, at each bit position, corresponding bits of said binary complements received into a second m-bit word;
- and
- (d) means coupled to said first and second receivers for translating the combined states of each i.sup.th bit of said first m-bit word and the corresponding i.sup.th bit of said second m-bit word into a value in a predetermined manner, and generating an m-bit group identifier of the requesting units based upon said translation.
A method of arbitrating simultaneous requests for access to a shared resource by a plurality of units, wherein each of said units is identified by a unique address identifier, said address identifiers each comprising a plurality of address bits, each of said address bits occupying a bit position, the method comprising:
- (a) a central arbitration module transmits an address identifier code to each of a plurality of units, wherein said address identifier code transmitted by said central arbitration module includes a plurality of address code bits, each occupying a bit position, some of which address code bits may represent a bit of any value;
- (b) each of said units requesting access to said shared resource and whose address identifier matches said transmitted address identifier code transmits to said central arbitration module its unique address identifier;
- (c) said central arbitration module examines the bits of all said transmitted address identifiers from said units to determine if any of said address identifier bits differ at corresponding bit positions;
- (d) if at a first bit position differing address identifier bits are detected, said central arbitration module establishes a new first address identifier bit for that bit position;
- (e) said central arbitration module transmits a new address identifier code incorporating said first established value at said first bit position, causing at least one of said requesting units that was previously addressed to not be addressed;
- (f) successively repeating steps (b) through (e) for those requesting units that are addressed in steo (e), successively excluding requesting units until said central arbitration module, in step (c), determines that at no bit positions of said address identifiers are there any differing address identifier bits, indicating that only one requesting unit remains.
Apparatus for arbitrating simultaneous requests for access to a shared resource by a plurality of units, wherein each of said units is identified by a unique address identifier, said address identifier comprising a plurality of address bits, each of said address bits occupying a bit position, the apparatus comprising:
- (a) a central arbitration module including a transmitter for transmitting an address identifier code to each of a plurality of units, wherein said address identifier code transmitted by said central arbitration module includes a plurality of address code bits, each occupying a bit position, some of which address code bits may represent a bit of any value;
- (b) an address identifier transmitter in each of said plurality of units that are requesting access to said shared resource and whose address identifier matches said transmitted address identifier code for transmitting to said central arbitration module its unique address identifier;
- (c) a receiver in said central arbitration module for receiving said transmitted address identifiers and examining the bits of all said transmitted address identifiers to determine if any of said address identifier bits differ at corresponding bit positions;
- (d) modifying means in said central arbitration module for establishing a new first address identifier bit for a first bit position of said first bit position differing address identifier bits are detected;
- and
- (e) wherein said transmitter of said central arbitration module transmits a new address identifier code incorporating said new first address identifier bit at said first bit position, to cause at least one of said requesting units that was previously addressed to not be addressed.
A method of arbitrating simultaneous requests for access to a shared resource by a plurality of units, wherein each of said units is identified by a unique address identifier, the method comprising:
- (a) a central arbitration module transmits an address code that addresses a set of units connected to a shared resource;
- (b) each unit in said addressed set that requests access to said shared resource transmits to said central arbitration module its address identifier;
- (c) said central arbitration module examines said address identifiers received from said units requesting access to said shared resource and determines if more than one unit in said addressed set is requesting access;
- (d) if said central arbitration module determines that more than one unit in said addressed set is requesting access, said central arbitration module modifies said address code to create a modified address code that addresses a subset of said addressed set of units and transmits said modified address code;
- (e) repeating steps (b) through (d) with the units of said subset that are requesting access to said shared resource and successive subsets of units each iteration that said central arbitration module determines in step (c) that more than one unit in said addressed subset is requesting access;
- (f) when said central arbitration module determines that only one unit of the addressed set or subset is requesting access to said shared resource, said central arbitration module grants access to said shared resource to said one unit requesting access.
Dependencies are inferred from the claim text.