System for combining a plurality of requests referencing a common target address into a single combined request having a single reference to the target address

Claim 2

In a parallel processing computer system having a plurality of components interconnected by a distribution system, each component having an identifier on the distribution system, a universal multiple-phase method of routing a plurality of requests, the requests originating from at least one source component having a source identifier and each request referencing a target address accessible by a target destination component having a target identifier, comprising the steps of: originating a first request from a first source component; redirecting, through a non-sorting function, the first request across the distribution system away from the target destination component and toward an intermediate destination component having an intermediate identifier not equal to the target identifier; combining a plurality of requests including the first request at the intermediate destination component into a single destination request formed for the target address, the single destination request having a single reference to the target address computed by operating on the references to the target address in the plurality of requests; and directing the destination request across the distribution system toward the target destination component having access to the target address.

Claim 3

The method according to claim 1 wherein the step of redirecting requests comprises selecting the intermediate destination component by a hashing process.

Claim 4

The method according to claim 1 wherein the step of combining requests comprises at least a second phase of further redirecting a second request across the distribution away from the target destination component and toward an intermediate destination component having an intermediate identifier not equal to the target identifier and further combining requests.

Claim 5

The method according to claim 1 wherein the step of redirecting a first request comprises determining the intermediate identifier dependent on the target address.

Claim 6

The method according to claim 4 wherein the step of determining is based partially on the target address and partially independent of the target address.

Claim 7

The method according to claim 5 wherein the intermediate identifier is partially based on the target address through a hash function.

Claim 8

The method according to claim 5 wherein the intermediate identifier is partially based on a substantially random choice.

Claim 9

The method according to claim 5 wherein the intermediate identifier is partially based on the source component.

Claim 10

In a parallel processing computer system having a plurality of components interconnected by a distribution system, each component having an identifier on the distribution system, a universal multiple-phase method of routing a plurality of requests, the requests originating from at least one source component having a source identifier and each request referencing a target address accessible by a target destination component having a target identifier, comprising the steps of: forming a destination request for a target address from at least one combined request, comprising at least one phase of the forming steps: redirecting, through a non-sorting function, a request across the distribution system away from the target destination component and toward an intermediate destination component having an intermediate identifier dependent on the target address of the request, the intermediate identifier not equal to the target identifier; and at the intermediate component, combining a plurality of received requests having a shared target address to form a single combined request, the single combined request having a single references to the target address computed by operating on the references to the target address in the plurality of received requests; and in a last phase, directing the destination request across the distribution system toward the target destination component having access to the target address.

Claim 11

In a parallel processing computer system having a plurality of components interconnected by a distribution system, each component having an identifier on the distribution system, a universal multiple-phase method of routing a plurality of requests, the requests originating from at least one source component having a source identifier and each request referencing a target address accessible by a target destination component having a target identifier, comprising the steps of: forming a destination request for a target address from at least one combined request, comprising at least one phase of the forming steps: redirecting, through a non-sorting function, a request across the distribution system away from the target destination component and toward an intermediate destination component having an intermediate identifier dependent on the target address of the request, the intermediate identifier not equal to the target identifier; and at the intermediate component, combining a plurality of received requests having a shared target address to form a single combined request, the single combined request having a single references to the target address computed by operating on the references to the target address in the plurality of received requests; and in a last phase, directing the destination request across the distribution system toward the target destination component having access to the target address.

Claim 12

The method according to claim 9 wherein the step of redirecting a request across the distribution system comprises determining the intermediate identifier based partially on the target address and partially independent of the target address.

Claim 13

The method according to claim 10 wherein the intermediate identifier is partially based on the target address through a hash function and partially based on a substantially random choice.

Claim 14

The method according to claim 11 wherein the intermediate identifier is partially based on the target address through a hash function and partially based on the source identifier.

Claim 15

The method according to claim 9 wherein the step of combining comprises performing commutative and associative operations on the requests that reference the same target address.

Claim 16

The method according to claim 9 wherein the step of directing the destination request comprises determining the respective target identifier using a hash function.

Claim 17

The method according to claim 9 wherein the step of directing the destination request comprises setting the target identifier to reference a component having access to the target address.

Claim 18

The method according to claim 9 further comprising the step of providing a basis sequence of m integers, there being one integer for a respective phase with a first integer corresponding to a first phase and a last integer corresponding to the last phase, each integer indicating the number of requests that can be combined for each respective phase, the product of the integers equaling the number of components on the system.

Claim 19

The method according to claim 16 wherein the step of providing a basis sequence comprises providing integers that are powers of 2.

Claim 20

In a parallel processing computer system having a plurality of components interconnected by a distribution system, each component having an identifier on the distribution system, a universal multiple-phase method of routing a plurality of requests, the requests originating from at least one source component having a source identifier and each request referencing a target address accessible by a target destination component having a target identifier, comprising the steps of: providing a basis sequence of m integers, there being one integer for a respective phase with a first integer corresponding to a first phase and a last integer corresponding to a last phase, each integer indicating the number of requests that can be combined for each respective phase; forming a destination request from at least one combined request, comprising m-1 phases of the forming steps: redirecting, through a non-sorting function, a request across the distribution system away from the target destination component and toward an intermediate component having an intermediate identifier dependent on the target address of the request, the intermediate identifier not equal to the destination identifier; at the intermediate component, receiving a plurality of requests which have traversed the distribution system; and at the intermediate component, combining a plurality of received requests having a shared target address using commutative and associative operations on the references to the target address in the plurality of requests to form a single combined request having a single reference to the target address; and in the m th phase, directing the destination request across the distribution system toward the target destination component having access to the target address.

Claim 21

In a parallel processing computer system having a plurality of components interconnected by a distribution system, each component having an identifier on the distribution system, a universal multiple-phase method of routing a plurality of requests, the requests originating from at least one source component having a source identifier and each request referencing a target address accessible by a target destination component having a target identifier, comprising the steps of: providing a basis sequence of m integers, there being one integer for a respective phase with a first integer corresponding to a first phase and a last integer corresponding to a last phase, each integer indicating the number of requests that can be combined for each respective phase; forming a destination request from at least one combined request, comprising m-1 phases of the forming steps: redirecting, through a non-sorting function, a request across the distribution system away from the target destination component and toward an intermediate component having an intermediate identifier dependent on the target address of the request, the intermediate identifier not equal to the destination identifier; at the intermediate component, receiving a plurality of requests which have traversed the distribution system; and at the intermediate component, combining a plurality of received requests having a shared target address using commutative and associative operations on the references to the target address in the plurality of requests to form a single combined request having a single reference to the target address; and in the m th phase, directing the destination request across the distribution system toward the target destination component having access to the target address.

Claim 22

The method according to claim 18 wherein the step of providing the basis sequence comprises providing integers that are powers of 2.

Claim 23

The method according to claim 18 wherein the step of redirecting a request across the distribution system comprises determining the intermediate identifier based partially on the target address and partially independent of the target address.

Claim 24

The method according to claim 20 wherein the intermediate identifier is partially based on the target address through a hash function and partially based on a substantially random choice.

Claim 25

The method according to claim 21 wherein the intermediate identifier is partially based on the target address through a hash function and partially based on the source component.

Claim 26

The method according to claim 18 wherein the step of directing the destination request comprises determining the target identifier using a hash function.

Claim 27

The method according to claim 18 wherein the step of directing the destination request comprises setting the target identifier to be a component having access to the target address.

Claim 28

A universal multiple-phase system for routing requests on a parallel processing computer, comprising: a plurality of components on the system, each component having an identifier on the system; a plurality of source requests, each source request originating from a source component and referencing a target address, the source requests being addressed by a plurality of source components to at least one selected component such that the selected components combine the source requests into at least one single combined request having a single reference to the target address by operating on the references to the target address in the plurality of source requests; and a distribution system interconnecting the components for directing the requests between components, each source request being redirected, through a non-sorting function, from the originating source component across the distribution system away from the target destination component having access to the target address and toward the associated selected component.

Claim 29

A universal multiple-phase system for routing requests on a parallel processing computer, comprising: a plurality of components on the system, each component having an identifier on the system; a plurality of source requests, each source request originating from a source component and referencing a target address, the source requests being addressed by a plurality of source components to at least one selected component such that the selected components combine the source requests into at least one single combined request having a single reference to the target address by operating on the references to the target address in the plurality of source requests; and a distribution system interconnecting the components for directing the requests between components, each source request being redirected, through a non-sorting function, from the originating source component across the distribution system away from the target destination component having access to the target address and toward the associated selected component.

Claim 30

The system according to claim 25 further comprising a basis sequence of integers for controlling the redirecting of requests, the basis sequence specifying the number of phases and the number of requests that can be combined in each phase.

Claim 31

The system according to claim 26 wherein: for at least one phase, the source requests are redirected based on the basis sequence to selected components having intermediate identifiers, where source requests that share a common target address are combined; and at the end of the at least one phase, destination requests are formed for the target addresses.

Claim 32

The system according to claim 27 wherein each destination request is routed to the target destination component having access to the target address.

Claim 33

The system according to claim 26 wherein each integer in the basis sequence is an even power of 2.

Claim 34

The system according to claim 25 wherein the phases are synchronous.

Claim 35

The system according to claim 25 wherein the phases are not synchronous.

Claim 36

The system according to claim 25 wherein the components comprise both processors and memory.

Claim 37

The system according to claim 32 wherein the target address is located within the address space of a target destination component.

Claim 38

The system according to claim 25 further comprising a hashing process to select the at least one selected component.

Claim 39

The system according to claim 25 wherein the distribution system is a point-to-point distribution system.

Claim 40

The system according to claim 35 wherein the point-to-point distribution system is a router.

Claim 41

The system according to claim 25 wherein the distribution system is an optical communications medium.

Claim 42

The system according to claim 25 wherein each component identifier is unique from all other component identifiers on the system.

Claim 43

The method according to claim 1 wherein each component identifier is unique from all other component identifiers on the distribution system.

Claim 44

The method according to claim 9 wherein each component identifier is unique from all other component identifiers on the distribution system.

Claim 45

The method according to claim 18 wherein each component identifier is unique from all other component identifiers on the distribution system.

Claim 46

The method according to claim 1 wherein the first request arrives unaltered at the intermediate destination component after traversing the distribution system.

Claim 47

The method according to claim 9 further comprising, at the intermediate component, the step of receiving the request after the request has traversed the distribution system.

Claim 48

The method according to claim 18 where the step of providing a basis sequence comprises providing integers having a product equaling the number of components on the computer system.

Claim 49

A universal multiple-phase system for routing requests on a parallel processing computer, comprising: a plurality of components for generating and processing requests, each component having a unique identifier on the system; a plurality of source requests, each source request originating from a source component from the plurality of components and referencing a target address, each source request being redirected by the respective source component toward at least one selected intermediate destination component from the plurality of components, each intermediate destination component selected for receiving a source request by a non-sorting hashing function based at least partially on the target address of the source request and not dependent on all requests currently in the computer, each intermediate destination component combining a plurality of received requests referencing a common target address into a single combined request referencing the common target address, the single combined request having a single reference to the common target address, the single combined request being computed by operating on the references to the target address in the plurality of received requests; and a distribution system interconnecting the components and optimized for routing the requests between components, each source request being redirected from the originating source component across the distribution system away from the target destination component and toward the addressed intermediate destination component, at least one source request arriving unaltered at the addressed intermediate destination component after traversing the distribution system.

Claim 50

A universal multiple-phase system for routing requests on a parallel processing computer, comprising: a plurality of components for generating and processing requests, each component having a unique identifier on the system; a plurality of source requests, each source request originating from a source component from the plurality of components and referencing a target address, each source request being redirected by the respective source component toward at least one selected intermediate destination component from the plurality of components, each intermediate destination component selected for receiving a source request by a non-sorting hashing function based at least partially on the target address of the source request and not dependent on all requests currently in the computer, each intermediate destination component combining a plurality of received requests referencing a common target address into a single combined request referencing the common target address, the single combined request having a single reference to the common target address, the single combined request being computed by operating on the references to the target address in the plurality of received requests; and a distribution system interconnecting the components and optimized for routing the requests between components, each source request being redirected from the originating source component across the distribution system away from the target destination component and toward the addressed intermediate destination component, at least one source request arriving unaltered at the addressed intermediate destination component after traversing the distribution system.

Claim 51

The system according to claim 45 wherein the combined request is redirected across the distribution system by the respective intermediate destination component to a component selected by the hashing function based on the common destination address, the combined request arriving unaltered at the selected component after traversing the distribution system.

Claim 52

The system according to claim 45 wherein the distribution system has an optimized path from the source component to the target destination component, the source request traversing a redirected path from the source component to the intermediate destination component, the optimized path not including the redirected path.