Abstract:
A method for fast booting an operation system on multiple processors coupled in multi-dimensional array architecture with higher efficiency and reliability. A particular PLEX™ node, which is designated as a primary boot master node, receives a sequence of data packets containing a boot image program to be used to boot the operating system. It first forwards a copy of each data packet to various selected neighboring nodes to which the primary boot master node is directly connected. The nodes that have received the data packets from the primary boot master node further forward the data packets to various other selected nodes, until all the PLEX™ nodes have succeeded in loading the entire boot image program. Three schemes are developed, which improve booting efficiency by allowing all PLEX™ nodes to receive the operating system as close to simultaneously as possible under certain constraints of the way that the PLEX™ nodes are interconnected.

Description:
CROSS-REFERENCE TO RELATED APPLICATION  
       [0001]    This application claims priority to U.S. Provisional Patent Application No. 60/346,899 filed on Jan. 8, 2002 (Attorney Docket No. AGLE0057PR). 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    1. Technical Field  
           [0003]    The invention relates generally to methods for initializing an operating system on multiprocessor system, and more particularly to a method for fast booting an operating system on communications processors coupled in a multi-dimensional array architecture.  
           [0004]    2. Description of Prior Art  
           [0005]    A computer operating system is an integrated set of specialized programs that is used to control the execution of application programs running on the computer. Typically, an operating system manages the interaction of the computer hardware and software by providing services to the software applications such as resource allocation, scheduling of tasks, data management and input and output (I/O) control. When a computer is turned on, the operating system is loaded into main computer memory by a set of instructions normally contained within ROM. This process is called booting or initial program loading. A single-processor computer usually undergoes a booting routine that is controlled by a computer program that performs various tasks such as loading an operating system into the memory, checking memory for defects, and loading software drivers needed for equipment associated with the computer.  
           [0006]    A multiprocessor computer, by definition, contains multiple processors that can execute multiple parts of a computer program or multiple programs simultaneously. In general, this parallel computing executes computer programs faster than conventional single processor computers that execute the parts of a program sequentially. When a multiprocessor computer system is first powered on or otherwise rest, the processors in the system are initialized by setting them to a known state. The reset causes a processor to jump to the system basic input/output systems (BIOS) to begin code execution. The BIOS brings the system through an initialization or booting procedure whereby diagnostic routines are run on the system hardware, such as memory and the processors. After the initialization or booting procedure is complete, an operation system is loaded onto the computer system.  
           [0007]    In a typical multiprocessor system, operating system allocates high-speed communication to one processor and uses the other processor for more computationally intensive tasks, such as image processing algorithms. Operating system often provides real-time event-driven software tools to aid in the control of such computing systems. Operating system may further provide real-time event-driven software tools supporting message passing to organize communication between concurrent tasks or objects, which may reside in different processors.  
           [0008]    As multiprocessor systems increase in complexity, the booting scheme correspondingly becomes more sophisticated. This is especially true for advanced multinode multiprocessor systems. Various booting methods have been developed. However, these methods are limited by the systems architecture. In other words, a booting scheme for one system architecture generally cannot be used in other system architecture.  
           [0009]    U.S. Pat. No. 5,867,702 discloses a method for initializing a multiprocessor system. The method includes providing a first portion of boot code to multiple processors for execution, selecting a first processor, the selection based on which of the multiple processors first successfully executes the first portion of the boot code, providing a second portion of the boot code only to the first processor, and the first processor executing the second portion of the boot code to configure the multiprocessor system.  
           [0010]    U.S. Pat. No. 5,938,765 discloses another method for initializing a shared-memory, multinode multiprocessor computer system. The nodes in the multiprocessor computer system separately and independently run standard PC-based BIOS routines in parallel for initialization of the nodes. These BIOS routines set addresses of hardware components on each node as though the nodes are in a single-node environment. After completion of BIOS, the addresses of the hardware components are reprogrammed to conform to the multinode environment. A master processor then takes control to boot the operating system on the multimode environment.  
           [0011]    U.S. Pat. No. 6,012,142 discloses another method for booting a multiprocessor system. The method includes transferring a message from external source through a first processor and from the first processor to a second processor, checking the message passed to the second processor without error, interpreting the message by a selected one of the first and second processors, and then performing boot operations by the selected processor in response to the interpretation of the message.  
           [0012]    U.S. Pat. No. 6,058,475 discloses another method of booting a computer containing more than two processors. If a normal boot attempt fails, different processors are selected, one-at-a-time, for performing the boot routine. During the boot routine, all other processors are held inactive. After boot, processors are tested for health. Non-healthy processors are held inactive, and healthy processors are activated as usual.  
           [0013]    These methods cannot be used or cannot be effectively used in initializing concurrent high-speed communication networks acting with multi-dimensional arrays of communications processors and nodes of such networks. What is desired is to develop an efficient and effective scheme for booting such networks.  
         SUMMARY OF THE INVENTION  
         [0014]    The invention provides a method for fast booting an operating system on multiple processors that are coupled in a multi-dimensional array architecture. The invention provides higher efficiency and reliability. The goal is to make a PLEX™ array of nodes load the operating system faster. The baseline case is ripple booting, in which a particular PLEX™ node loads and executes the operating system, then various selected neighboring nodes load the operating system with the help of that first node, and so on until all the PLEX™ nodes have succeeded in loading the operating system from their immediate neighbors. Three schemes are developed, which improve booting efficiency by allowing all PLEX™ nodes to receive the operating system as close to simultaneously as possible under certain constraints of the way that the PLEX™ nodes are interconnected.  
           [0015]    In Scheme A, the designated primary boot master node (P node) receives a sequence of data packets containing a boot image program from an external source such as a disk or another PLEX™ array and forwards the data packets to several secondary boot master nodes (S nodes). Communicatively, the S nodes are those that are directly coupled to the P node; geometrically, they are those that in a same row or same column with the P node. Then, the S nodes forward the data packets to the rest of the nodes, i.e., the tertiary nodes (T nodes) in such a way that if an S node is in a same row as the P node, then it forwards the data packet to the T nodes in a same column with this S node. If an S node is in a same column as the P node, then it forwards the data packets to the T nodes in a same row with this S node.  
           [0016]    In Scheme B, the first forwarding stage is same as that in Scheme A. In the second stage, however, the S nodes perform the forwarding operations not only in the orthogonal direction as in Scheme A, but also in the direction along which they received the data packets. This scheme further increases fault tolerance because it permits an S node to receive the data packets in case where a link between the P node and the S node fails.  
           [0017]    In Scheme C, the P node first forwards the data packets to the nodes that are in a same row as the P node. In the second stage, each S node forwards the data packets to the T nodes which are in a same column with the S node, and the P node, acting as an S node, further forwards the data packets to the T nodes which are in a same column with the P node. 
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0018]    [0018]FIG. 1A is a block diagram illustrating an example architecture of a multiprocessor engine comprising a two-dimensional PLEX™ array of 4×4 nodes in accordance with the preferred embodiment;  
         [0019]    [0019]FIG. 1B is a block diagram illustrating the inner structure of a typical node in the PLEX™ array of FIG. 1A;  
         [0020]    [0020]FIG. 2A is a schematic diagram illustrating the first stage of the booting process where the primary boot master node (P) forwards a sequence of data packets containing a boot image program to the secondary boot master nodes (S) which are communicatively coupled to the primary boot master node (P) according to Scheme A of this invention;  
         [0021]    [0021]FIG. 2B is a schematic diagram illustrating the second stage of the booting process where each secondary boot master node (S) forwards the data packets to the tertiary nodes to which it is directly connected and which lie in the orthogonal direction from which the S node received the program according to Scheme A;  
         [0022]    [0022]FIG. 2C is a flow diagram illustrating the booting sequence according to Scheme A;  
         [0023]    [0023]FIG. 3A is a schematic diagram illustrating the first stage by solid line and the second stage by dashed line of the booting process according to Scheme B;  
         [0024]    [0024]FIG. 3B is a flow diagram illustrating the booting sequence according to Scheme B;  
         [0025]    [0025]FIG. 4A is a schematic diagram illustrating the first stage of the booting process where the primary boot master node (P) forwards a sequence of data packets containing a boot image program to the nodes which are in the same row as the primary boot master node (P) according to Scheme C;  
         [0026]    [0026]FIG. 4B is a schematic diagram illustrating the second stage of the booting process where each secondary boot master node (S) forwards the data packets to the nodes in the same column as this secondary boot master node (S) according to Scheme C;  
         [0027]    [0027]FIG. 4C illustrates an equivalent of Scheme C where the primary boot master node (P) first forwards the data packets to the nodes in the same column as the primary boot master node (P); and  
         [0028]    [0028]FIG. 4D is a flow diagram illustrating the method according to Scheme C. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0029]    PLEX™ Array Architecture of Multiprocessor System  
         [0030]    Illustrated in FIG. 1A is an example architecture  10  of a multiprocessor engine comprising a two-dimensional PLEX™ array of 4×4 nodes in accordance with the preferred embodiment. In this architecture, each node is communicatively coupled to the nodes located in a same row with it and to the nodes located in a same column with it. FIG. 1B is a block diagram illustrating the inner structure of node  11  as an example of a typical node in the PLEX™ array of FIG. 1A. Each node includes two processors  112 ,  114  and six ports  115 . Each processor is coupled to an independent RAM  111 ,  113  and three ports  115 .  
         [0031]    The architecture  10  may have M orthogonal directions that support communications between an M dimensional lattice of up to N{circumflex over ( )}M nodes, where M is at least two and N is at least four. Each node pencil in a first orthogonal direction contains at least four nodes and each node pencil in a second orthogonal direction contains at least two nodes. Each of the nodes contains a multiplicity of ports.  
         [0032]    As used herein, a nodal pencil refers to a 1-dimensional collection of nodes differing from each other in only one dimensional component, i.e. the orthogonal direction of the pencil. By way of example, a nodal pencil in the first orthogonal direction of a two-dimensional array contains the nodes differing in only the first dimensional component. A nodal pencil in the second orthogonal direction of a two-dimensional array contains the nodes differing in only the second dimensional component.  
         [0033]    The architecture  10  represents a communications network that is comprised of a communication grid interconnecting the nodes. The communications grid includes up to N{circumflex over ( )}(M−1) communication pencils, for each of the M directions. Each of the communication pencils in each orthogonal direction corresponds to a node pencil containing a multiplicity of nodes, and couples every pairing of nodes of the node pencil directly.  
         [0034]    As used herein, communication between two nodes of a nodal pencil coupled with the corresponding communication pencil comprises traversal of the physical transport layer(s) of the communication pencil.  
         [0035]    Such embodiments of the invention advantageously support direct communication between any two nodes belonging to the same communication pencil, supporting communication between any two nodes in an M dimensional array in at most M hops.  
         [0036]    Scheme A  
         [0037]    [0037]FIG. 2A is a schematic diagram of FIG. 1A illustrating a two-dimensional PLEX™ array of interconnected nodes wherein the dashed lines represent the first forwarding stage of the booting process according to Scheme A. Scheme A starts with designating one of the nodes, for example, node  32 , as a primary boot master node (P 32 ). This node is usually an I/O node or control node, but it can be any node that gets data from an external source such as a disk or a link to another array of processors. The nodes that are directly connected to P 32  are designated as secondary boot masters (S nodes). In a typical two-dimensional PLEX™ array architecture, the S nodes are those in the same row as the primary boot master and also those in the same column. For instance, nodes  12 ,  22 ,  42 ,  31 ,  33 ,  34 , are directly connected nodes of the primary boot master node P 32 . In the first stage, as the dashed lines indicated, P 32  forwards a sequence of data packets containing a boot image program to the S nodes: P 32 →S 31 ; P 32 →S 33 ; P 32 →S 34 ; P 32 →S 22 ; P 32 →S 42 ; and P 32 →S 12 . A data packet is a unit of content information enclosed in a wrapper that is used for convenience in transporting it. The boot image program is usually too large to be carried by one data packet. To transmit the entire boot image program, it must be broken down into small portions and each portion is enclosed in a wrapper. In this way, the entire boot image program is carried in a sequence of data packets. When the sequence of data packets is received, the program portions contained in the wrappers are combined back to the program and the wrappers are discarded.  
         [0038]    In the first stage, P 32  receives the data packets from an external source. It stores each received data packet in memory for later use in starting the operating system, and at the same time forwards each received data packet to the secondary boot masters. As a general rule, a second node does not send back the data packet to a first node from which the second node received the data packet. Here, the secondary boot masters S 12 , S 22 , S 42 , S 31 , S 33 , S 34  do not send the data packet back to the primary boot master P 32 .  
         [0039]    [0039]FIG. 2B illustrates the second stage of Scheme A where each S node forwards each received data packet to the directly connected nodes along the orthogonal direction. Each S node receives a data packet from the primary boot master P 32 , stores it in memory for later use, and at the same time forwards it to tertiary nodes (T nodes) to which the S node is directly connected and which lie in the orthogonal direction from which the S node received the data packet. As the dashed line indicated, an S node, which is in the same row of the primary boot master P 32 , forwards the data packet to the other nodes that are in the same column as the S node, i.e. S 31 →T 41 , T 21 , T 11 ; S 33 →T 43 , T 23 , T 13 ; S 34 →T 44 , T 24 , T 14 . Similarly, an S node, which is in the same column as the primary boot master P 32 , forwards the data packet to the other nodes in the same row as the S node, i.e. S 42 →T 41 , T 43 , T 44 ; S 22 →T 21 , T 23 , T 24 ; S 12 →T 11 , T 13 , T 14 . As a general rule, an S node does not forward the data packet to the nodes in the same row or the same column as the primary boot master P 32 . Here, S 34  does not forward the data packet to S 33 ; S 12  does not forward the data packet to S 22 . The receiving and forwarding process is repeated until the entire sequence of data packets representing the entire boot image program is received and forwarded.  
         [0040]    [0040]FIG. 2C is a flow diagram illustrating the booting process according to Scheme A. The process includes the steps of:  
         [0041]    [0041] 201 : The primary boot master node (P) receives a data packet containing a portion of a boot image program from an external source. (The boot image program is transported by a sequence of data packets, each of which contains a portion of the program;)  
         [0042]    [0042] 202 : The P node stores the data packet in its memory for use in later starting the operating system;  
         [0043]    [0043] 203 : At the same time with  202 , or immediately thereafter, the P node forwards the data packet to the secondary boot master nodes (S) to which it is directly connected, i.e. the nodes located in the same row and the nodes in the same column as the P node;  
         [0044]    [0044] 204 : Each S node stores the data packet in its memory for use in later starting the operating system;  
         [0045]    [0045] 205 : At the same time with  204 , or immediately thereafter, each S node forwards the data packet to the tertiary nodes (T) to which the S node is directly connected and which lie in the orthogonal direction from which the S node received the data packets;  
         [0046]    [0046] 205 A: Repeat steps  201 - 205  until the entire boot image program has been received and forwarded; and  
         [0047]    [0047] 206 : Start the operation system on each node.  
         [0048]    Note that T nodes need not forward the data packets to any other nodes; they simply store the data packets in memory for later use. Each T node receives two copies of the data packets and may discard one copy.  
         [0049]    With this scheme, all nodes in the PLEX™ array can receive the data packets at most two forwardings. An advantage of this scheme is that each T node receives packets from two different neighbors. This increases reliability in the presence of link faults. Another feature of this scheme is that the links between the P node and the various S nodes are idle during the second forwarding stage. For systems where the forwarding cannot be done simultaneously with the reception of the same data packet over the incoming link, i.e. the data packet must be received completely, stored, then forwarded, these idle links could be used to pipeline the first stage forwarding of the next data packet during the time that the second stage forwarding of the preceding data packet is occurring.  
         [0050]    Scheme B  
         [0051]    [0051]FIG. 3A illustrates a booting process according to Scheme B, which is a variation of Scheme A. With the first stage in Scheme A, the P node, for example, node  32 , forwards a sequence of data packets containing a boot image program to the S nodes, i.e. those in the same row as the P node and those in the same column as the P node. In the second stage, the S nodes perform the second forwarding operations not only in the orthogonal direction as in Scheme A, but also in the direction along which they received the data packets.  
         [0052]    Scheme B further increases fault tolerance because it permits some S nodes to receive the data packets in cases where a link between the P node and the S node fails. For example, if the P 32 →S 12  link fails, S 12  may receive the data packets from S 22 ; and if the P 32 →S 34  link fails, S 34  may receive the data packets from S 33 . FIG. 3B is a flow diagram illustrating the process according to Scheme B. The process includes the steps of:  
         [0053]    [0053] 301 : The Primary boot master node (P) receives a data packet containing a portion of a boot image program from an external source. (The boot image program is transported by a sequence of data packets, each of which contains a portion of the program;)  
         [0054]    [0054] 302 : P node stores the data packet in its memory for use in later starting the operating system;  
         [0055]    [0055] 303 : At the same time with  302 , or immediately thereafter, P node forwards the data packet to the secondary boot master nodes (S) to which it is directly connected, i.e. the nodes located in the same row and the nodes in the same column as the P node;  
         [0056]    [0056] 304 : Each S node stores the data packets in its memory for use in later starting the operating system;  
         [0057]    [0057] 305 : At the same time with  304 , or immediately thereafter, each S node forwards the data packet to the nodes (T) to which it is directly connected and which lie in the orthogonal direction along which the S node received the data packet and to the nodes (T) to which it is directly connected and which lie in the direction along which the S node received the data packet;  
         [0058]    [0058] 305 A: Repeat steps  301 - 305  until the entire boot image program has been received and forwarded; and  
         [0059]    [0059] 306 : Start the operation system on each node.  
         [0060]    Scheme C  
         [0061]    In Scheme C, P 32  first forwards a sequence of data packets containing a boot image program to the nodes in the same row as P 32 ; and then each S node (P 32  acts as an S node) forwards the data packets to the nodes in the same column as the S node. FIG. 4A illustrates the first stage of Scheme C where P 32  forwards the data packets first along a row (P 32 →S 31 , S 33 , S 34 ). FIG. 4B illustrate the second stage where P 32  and the S nodes forward the data packets to the T nodes in the same column (S 31 →T 41 , T 21 , T 11 ; P 32 →T 42 , T 22 , T 12 ; S 33 →T 43 , T 23 , T 13 ; S 34 →T 44 , T 24 , T 14 ).  
         [0062]    In Scheme C, only those nodes in the same row as P 32  are designated as S nodes. At the second forwarding stage, P 32  itself must take the role of an S node and forward along its column. Note that this scheme works equally well by reversing the roles of row and column.  
         [0063]    [0063]FIG. 4C illustrates an equivalent of Scheme C where P 32  first forwards the data packets to the nodes in the same column as P 32 ; and then each S node (P node  32  acts as an S node) forwards the data packets to the nodes in the same row as the S node. The solid lines represent the first forwarding (P 32 →S 42 , S 22 , S 12 ) and the dashed lines represent the second forwarding (S 12 →T 11 , T 13 , T 14 ; S 22 →T 21 , T 23 , T 24 ; P 32 →T 31 , T 33 , T 34 ; S 32 →T 41 , T 43 , T 44 ).  
         [0064]    An advantage of Scheme C is that P 32  does not need to forward 6 packets, i.e. the packets to nodes  31 ,  33 ,  34 ,  12 ,  22 ,  42  as in Scheme A or B at once at the first forwarding stage. This may be important if the P node is incapable of simultaneously forwarding along rows and columns.  
         [0065]    [0065]FIG. 4D is a flow diagram illustrating the process according to Scheme C. The process includes the steps of:  
         [0066]    [0066] 401 : The Primary boot master node (P) receives a data packet containing a portion of a boot image program from an external source. (The boot image program is transported by a sequence of data packets, each of which contains a portion of the program;)  
         [0067]    [0067] 402 : The P node stores the received data packet in its memory for use in later starting the operating system;  
         [0068]    [0068] 403 : At the same time with  402 , the P node forwards the received data packet to the secondary boot master nodes (S) to which it is directly connected and which lie in same row as the P node;  
         [0069]    [0069] 404 : Each S node stores the received data packet in its memory for use in later starting the operating system;  
         [0070]    [0070] 405 : At the same time with  404 , each S node forwards the received data packet to the T nodes to which it is directly connected and which lie in the same column with it. In this stage, the P node acts as an S node;  
         [0071]    [0071] 405 A: Repeat steps  301 - 305  until the entire boot image program has been received and forwarded; and  
         [0072]    [0072] 406 : Start the operation system on each node.  
         [0073]    Hop Counting  
         [0074]    Each data packet that carries a portion of the data packets may contain a hop count field that is incremented each time the data packet is forwarded. That permits an S node under Scheme B to determine that it has received a second-stage packet for the first time, in which case it must have missed the first stage packet that was sent to it directly from the P node. In this case, where the S node has not fulfilled its duty to send second-stage packets to its “T” neighbors, and it can fulfill that duty by sending third stage packets to them.  
         [0075]    Further forwarding stages are possible, but are likely to be unnecessary for the usual case where most of the links are good.  
         [0076]    Geometric Determination  
         [0077]    Given the row, column location (“address”) of the primary boot master node P, which can be stored in the data packets, each node can determine its role in the process by comparing its own address to P&#39;s address. Hop counting is not strictly necessary if a node can determine on which links a packet arrived and compare that to the expected arrival links based on that node&#39;s role.  
         [0078]    If P&#39;s address is designated Rp, Cp (row and column) and a given N&#39;s address is Rn, Cn, Table 1 shows a node&#39;s role under Scheme A and Scheme B; Table 2 shows a node&#39;s role under Scheme C when S nodes are in the same row as the P node; and Table 3 shows a node&#39;s role under Scheme C when S nodes are in the same column as the P node.  
                             TABLE 1                           Scheme A and Scheme B            Rn (Node&#39;s Row Address)   Cn (Node&#39;s Column Address)   Role               Rp   Cp   P       Rp   Not Cp   S       Not Rp   Cp   S       Other wise       T                  
 
         [0079]    [0079]                             TABLE 2                           Scheme B (Row First)            Rn (Node&#39;s Row Address)   Cn (Node&#39;s Column Address)   Role               Rp   Cp   P       Rp   Not Cp   S       Other wise       T                    
         [0080]    Table 3. Scheme B (Column First)  
                             TABLE 3                           Scheme B (Column First)            Rn (Node&#39;s Row Address)   Cn (Node&#39;s Column Address)   Role               Rp   Cp   P       Not Rp   Cp   S       Other wise       T                  
 
         [0081]    Acknowledgment Packets  
         [0082]    The three schemes described herein can operate with explicit acknowledgement packets, in which case the acknowledgment packets can travel in the reverse direction along a link from which the packet came from. Another possibility is to dispense with acknowledgements. Any node that loses a packet or otherwise fails to keep up can stop and use other protocols later to complete its booting process.  
         [0083]    An intermediate scheme is to use the acknowledgements to insure the completion of the P-to-S node transfers, but to leave the second stage (S-to-T) node transfers unacknowledged.  
         [0084]    Third Stage Forwarding  
         [0085]    After the second stage nearly all the nodes have a copy of the data packets representative of the boot image program. An additional elaboration, which provides even greater reliability, is to use an extra “third stage” forwarding step. In one embodiment for a third stage, all nodes forward the data packets on all the nodes to which they are directly connected. This results in a very high probability of reaching every node.  
         [0086]    It is needless to forward the data packets to the nodes that are known to have the data packets already, i.e. the nodes from which a data packet was received in the previous stage.  
         [0087]    RAM Disk Kernel Booting  
         [0088]    The effectiveness of a broadcast booting scheme such as this is increased by being able to send to many nodes all the data that they need to get them completely up and running. The data includes not only the operating system kernel, but also all the files the nodes need to access during the operating system&#39;s initialization and startup phase.  
         [0089]    For this reason, the collection of files that is sent could be structured as a ramdisk image of the portion of the root file system that is accessed during startup. In the case that the PLEX™ array contains nodes of different types, the data collection may include the superset of all the files needed by any of those node types.  
         [0090]    The methods described herein can be embodied in a set of computer readable instructions or codes which can be stored in any computer readable storage medium and can be transferred and downloaded over the Internet.  
         [0091]    Although the invention is described herein with reference to the preferred embodiment, one skilled in the art will readily appreciate that other applications may be substituted for those set forth herein without departing from the spirit and scope of the present invention.  
         [0092]    Accordingly, the invention should only be limited by the claims included below.