公开(公告)号：US5083265A

公开(公告)日：1992-01-21

申请号：US510090

申请日：1990-04-17

申请人： Leslie G. Valiant

发明人： Leslie G. Valiant

IPC分类号： G06F9/46 ,  G06F15/173

CPC分类号： G06F9/52 ,  G06F15/17368

摘要： In accordance with the present invention, system architecture and programming are in accordance with a bulk-synchronous parallel processing model. Data is distributed to memory elements through a hashing function performed in individual hardware modules associated with computational elements. The router operates independently of the computational and memory elements and masks any substantial latency it may have by pipelining. A synchronizer provides for bulk synchronization in supersteps of multiple computational steps. The router bandwidth is balanced with that of the computational elements and the program may be compiled to a number of virtual processors significantly greater than the number of actual processors in the system.

摘要翻译： 根据本发明，系统架构和编程符合大容量同步并行处理模型。 通过在与计算元件相关联的各个硬件模块中执行的散列函数将数据分配到存储器元件。 路由器独立于计算和存储器元件操作，并且屏蔽通过流水线化可能产生的任何实质的延迟。 同步器在多个计算步骤的超级步骤中提供批量同步。 路由器带宽与计算元素的带宽平衡，并且程序可以被编译成明显大于系统中实际处理器数量的多个虚拟处理器。

公开(公告)号：US06763519B1

公开(公告)日：2004-07-13

申请号：US09305570

申请日：1999-05-05

申请人： William F. McColl ,  Jonathan M. D. Hill ,  Leslie G. Valiant ,  Stephen R. Donaldson

发明人： William F. McColl ,  Jonathan M. D. Hill ,  Leslie G. Valiant ,  Stephen R. Donaldson

IPC分类号： G06F946

CPC分类号： G06F9/5044 ,  G06F2209/5014

摘要： A multiprogrammed multiprocessor system comprises a plurality of processors and some communications resources such as networks through which the processors communicate with each other. A plurality of tasks may be executed on the system, and the allocation of the communications resources among the tasks is globally controlled. The allocation of resources among the tasks running on the system can be dependent on the signature of the tasks, where one component of a task signature is a measure of the communication resources needed by the task. The scheduling of a task running on the system may also be dependent on the signature of the task. The allocation of communications resources can be globally controlled using a variety of techniques including: packet injection into the communications resources using periodic strobing or using global flow control; using global implicit acknowledgments; by destination scheduling; by pacing; or by prioritized communication scheduling. Error recovery overheads can be amortized over a plurality of jobs running at one node. A user interface allows a plurality of service level options to be specified by a user, where the system can guarantee that the service levels can be achieved. Application users as well as system administrators can choose options as are appropriate. The user interface can allow the system administrator to run a scheduling mechanism that distributes communications resources among the tasks according to a market mechanism. The user interface can also allow a task to be guaranteed a fixed fraction of the resources independent of the other tasks then running or to be run as an interactive continuous job at one of a plurality of service levels. Finally, the user interface allows a system administrator to subdivide system resources into reserved and unreserved components, where the unreserved component is made available according to a market mechansim.

公开(公告)号：US5608870A

公开(公告)日：1997-03-04

申请号：US459367

申请日：1995-06-02

申请人： Leslie G. Valiant

发明人： Leslie G. Valiant

IPC分类号： G06F15/173 ,  G06F15/16 ,  G06F13/20

CPC分类号： G06F15/17393

摘要： 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.

摘要翻译： 请求在使用多相组合的并行计算系统中的组件之间路由。 在第一阶段，原始请求被分解成共享相同目的地址的请求组。 每个组中的请求在中间组件中组合成每组一个请求。 在后续阶段，组合请求本身分组并组合在中间组件中。 在最后阶段，组合请求由包含目标地址的组件处理。 中间组件的地址部分地由目的地地址上的散列和部分由分配功能决定。 中间组件地址的散列部分趋向于在每个阶段期间将组合的请求收敛到目标组件。 中间组件地址的分配部分倾向于在各个组件之间均匀分配工作负载。