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

• US 5,608,870 A
• Filed: 06/02/1995
• Issued: 03/04/1997
• Est. Priority Date: 11/06/1992
• Status: Expired due to Fees

• Current Assignee: President and Fellows of Harvard College (Harvard Corporation)
• Original Assignee: President and Fellows of Harvard College (Harvard Corporation)
• Inventors: Valiant, Leslie G.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Krick, Rehana P.
• Application Number:
  US08/459,367
• Time in Patent Office: 641 Days
• Field of Search: 395/200.1, 395/800, 395/410, 395/823, 340/825, 340/825.52
• US Class Current: 711/100
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining

Abstract

Requests are routed between components in a parallel computing system using multiple-phase combining. In the first phase, the original requests are decomposed into groups of requests that share the same destination address. The requests in each group are combined at an intermediate component into a single request per group. In subsequent phases, the combined requests are themselves grouped and combined in intermediate components. In the final phase, the combined requests are processed by the component containing the destination address. The addresses of the intermediate components are determined in part by hashing on the destination address and in part by a distributing function. The hashed portion of the intermediate component address tends to converge the combined requests toward the destination component during each phase. The distributing portion of the intermediate component address tends to distribute the workload evenly among the components.

Claims

1. 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.

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

3. 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.

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

5. 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.

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

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

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

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

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

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

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

15. 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.

16. 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.

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

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

43. 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.

18. 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.

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

20. 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.

21. 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.

22. 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.

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

24. 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.

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

44. 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.

25. 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.

26. 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.

27. 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.

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

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

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

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

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

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

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

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

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

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

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

45. 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.

46. 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.

47. 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.