Loading patent…
AssigneeMassively Parallel Technologies, Inc.
InventorsKevin David Howard, Glen Curtis Rea, Nick Wade Robertson, Silva Chang
Estimating the term…
Methods and systems for parallel computation of an algorithm using a plurality of nodes configured as a Howard Cascade. A home node of a Howard Cascade receives a request from a host system to compute an algorithm identified in the request. The request is distributed to processing nodes of the Howard Cascade in a time sequence order in a manner to minimize the time to so expand the Howard Cascade. The participating nodes then perform the designated portion of the algorithm in parallel. Partial results from each node are agglomerated upstream to higher nodes of the structure and then returned to the host system. The nodes each include a library of stored algorithms accompanied by data template information defining partitioning of the data used in the algorithm among the number of participating nodes.
A parallel processing system, comprising:
A method for processing a context-based algorithm for enhanced parallel processing within a parallel processing architecture, comprising the steps of:
A method for parallel processing an algorithm for use within a Howard Cascade, comprising the steps of:
A method for parallel computation comprising:
A method of distributing an algorithm computation request comprising:
A method for distributing an algorithm computation request for a complex algorithm in a parallel processing system comprising:
A method for parallelizing an algorithm comprising:
A computer readable storage medium tangibly embodying program instructions for a method for parallel computation, the method comprising:
A computer readable storage medium tangibly embodying program instructions for a method of distributing an algorithm computation request, the method comprising:
A computer readable storage medium tangibly embodying program instructions for a method for distributing an algorithm computation request for a complex algorithm in a parallel processing system, the method comprising:
A computer readable storage medium tangibly embodying program instructions for a method for parallelizing an algorithm, the method comprising:
A system for parallel computation comprising:
A system of distributing an algorithm computation request comprising:
A system for distributing an algorithm computation request for a complex algorithm in a parallel processing system comprising:
A system for parallelizing an algorithm comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Backward citations are indexed for grants only.
Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous…:…
Compilation: exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
The resource being a machine, e.g. CPUs, Servers, Terminals: considering hardware capabilities
Partitioning or combining of resources: algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs
Term end not estimated
Prior art programming methods are implemented with parallel processing architectures called “clusters.” Such clusters are generally one of two types: the shared memory cluster and the distributed memory cluster. A shared memory cluster consists of multiple computers connected via RAM memory through a back plane. Because of scaling issues, the number of processors that may be linked together via a shared back plane is limited. A distributed memory cluster utilizes a network rather than a back plane. Among other problems, one limitation of a distributed memory cluster is the bandwidth of the network switch array.
More particularly, each node of an N-node distributed memory cluster must obtain part of an initial dataset before starting computation. The conventional method for distributing data in such a cluster is to have each node obtain its own data from a central source. For problems that involve a large dataset, this can represent a significant fraction of the time it takes to solve the problem. Although the approach is simple, it has several deficiencies. First, the central data source is a bottleneck: only one node can access the data source at any given time, while others nodes must wait. Second, for large clusters, the number of collisions that occur when the nodes attempt to access the central data source leads to a significant inefficiency. Third, N separate messages are required to distribute the dataset over the cluster. The overhead imposed by N separate messages represents an inefficiency that grows directly with the size of a cluster; this is a distinct disadvantage for large clusters.
Shared memory clusters of the prior art operate to transfer information from one node to another as if the memory is shared. Because the data transfer cost of a shared memory model is very low, the data transfer technique is also used within clustered, non-shared memory machines. Unfortunately, using a shared memory model in non-shared memory architectures imposes a very low efficiency; the cluster inefficiency is approximately three to seven percent of the actual processor power of the cluster.
FIG. 1 is a block diagram of a prior art parallel processing cluster that processes an application running on a remote host.
FIG. 2 is a block diagram illustrating further detail of the prior art cluster, application and remote host of FIG. 1.
FIG. 3 schematically illustrates algorithm partitioning and processing through the prior art remote host and cluster of FIG. 1, FIG. 2.
FIG. 1 shows a block diagram illustrating a prior art parallel processing cluster 10 that processes a parallel application 28 operating on a remote host 26. As those skilled in the art appreciate, cluster 10 is for example a Beowulf cluster that connects several processors 12 together, through a communication channel 14 and a switch 16, to process parallel application 28. The number N of processors 12 is carefully matched to cluster type, e.g., sixteen processors for a Beowulf cluster. Remote host 26 communicates with cluster 10 via a data path 18 to access the collective computing power of processors 12 within cluster 10 to run parallel application 28, with a goal of reducing the execution time of parallel application 28.
FIG. 2 shows parallel processing application 28 using cluster 10 in more detail. Nodes 15(1), 15(2), 15(3) . . . 15(N) represent processors 12, FIG. 1, connected together via communication channel 14 that facilitates the movement of computer programs, data, and inter-process messages through nodes 15. As those skilled in the art appreciate, communication channel 14 may consist of computer buses, network linkages, fiber optic channels, Ethernet connections, switch meshes (e.g., switch 16, FIG. 1) and/or token rings, for example. Cluster 10 further has a gateway 24 that provides an interface to cluster 10. Gateway 24 typically provides one or more interfaces—such as a network interface 30, an Internet interface 34, and a peer-to-peer interface 35—to communicate with remote host 26 through a cluster boundary 36.
Remote host 26 is for example a computer system that runs parallel application 28. Illustratively, FIG. 2 shows application 28 and remote host 26 connected to gateway node 24 through network interface 30. In operation, gateway 24 enables communication between parallel application 28, running on host 26, and individual processing nodes 15 within cluster 10. Application 28 loads algorithm code and data onto individual processing nodes 15 prior to parallel processing of the algorithm code and data.