An alternative form of multiprocessors to a shared memory multiprocessor can be created by connecting completer computers through an interconnection network. Each computer consists of a processor and local memory but this memory is not accessible by other processors.
The interconnection network provides for processors to send messages to other processors. The message carry data from one processor to another as dictated by the program. Such multiprocessor systems are usually called message-passing multiprocessor, or simply multicomputers, especially if they consist of self-contained computers that could operate separately.
Programming a message-passing multicomputer still involves dividing the problem into parts that are intended to be executed simultaneously to solve the problem. Programming could use a parallel or extended sequential language, but a common approach is to use message-passing library routines that are inserted into a conventional sequential program for message-passing. Often, we talk in terms of processes. A problem is divided into a number of concurrent processes than computers, more than one process would be executed on one computer, in a time-shared fashion.
Processes communicate by sending messages; this will be the only way to distribute data and results between processes.
The purpose of the interconnection network is to provide a physical path for message sent from one computer to another computer.
Key issues in network design are the bandwidth, latency and cost.
The bandwidth is the number of bits that can be transmitted in unit time, given as bits/sec.
The network latency is the time to make a message transfer through the network.
The communication latency is the total time to send the message, including the software overhead and interface delays.
Message latency, or startup time, is the time to send a zero-length message, which is essentially the software and hardware overhead in sending a message(finding the route, packing, unpacking, etc) onto which must be added the actual time to send the data along the interconnection path.
The number of physical links in a path between two nodes is an important consideration because it will be a major factor in determining the delay for a message. The diameter is the minimum number of links between the two farthest nodes(computers) in the network. Only the shortest routes are considered. How efficiently a parallel problem can be solved using a multicomputer with a specific network is extremely important. The diameter of the network gives the maximum distance that a single message must travel and can be used to find the communication lower bound of some parallel algorithms.
A two dimensional mesh can be created by having each node in two dimensional array connect to its four nearest neighbors.
The mesh and torus network are popular because of their ease of layout and expandability. If necessary, the network can be folded; that is, rows are interleaved and columns, are interleaved so that the wraparound connections simply turn back through the network rather than stretch from one edge to the opposite edge.
BlueGene/L uses a three-dimensional (3D) torus network in which the nodes (red balls) are connected to their six nearest-neighbor nodes in a 3D mesh. In the torus configuration, the ends of the mesh loop back, thereby eliminating the problem of programming for a mesh with edges. Without these loops, the end nodes would not have six near neighbors.