Patent Publication Number: US-8126696-B1

Title: Modifying length of synchronization quanta of simulation time in which execution of nodes is simulated

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application Ser. No. 61/091,397, filed Aug. 24, 2008, titled “Modifying Length Of Synchronization Quanta Of Simulation Time In Which Execution Of Nodes Is Simulated” 
     BACKGROUND 
     Some types of computing systems have a number of nodes. A node may include one or more processors, and may also include its own memory and/or storage devices. For example, a multiple-node computing system may include a number of discrete computing devices, such as server computing devices, which correspond to the nodes of the computing system. As another example, a multiple-node computing system may include a number of processors within a single integrated circuit (IC) chip, which is commonly referred to as chip multiprocessors (CMP&#39;s). The processors on such an IC chip may be divided over a number of nodes of the multiple-node computing system, where each node includes one or more of the processors on the IC chip. 
     Simulating the execution of a multiple-node computing system can be difficult. While the nodes of such a computing system may execute in parallel with one another, at times the nodes may send inter-node data packets to each other that require simulation of their execution to be synchronized. If the timing of the inter-node data packets is ignored—i.e., when the inter-node data packets are received by their destination nodes—then simulation can occur more quickly, but simulation accuracy suffers. By comparison, if the timing of the inter-node data packets is always accounted for, then simulation accuracy can be guaranteed, but simulation completion time suffers. 
     SUMMARY 
     A method according to an embodiment of the present disclosure is for simulating execution of nodes interconnected by a network. The method simulates substantially parallel execution of the nodes during a current quantum of simulation time having a quantum length. Simulation of execution can result in simulation of inter-node data packets being transmitted over the network. Where the current quantum of simulation time has elapsed, the method synchronizes simulation of execution of the nodes. If no inter-node data packets were transmitted in simulation during the current quantum of simulation time, then the method increases the quantum length. If one or more inter-node data packets were transmitted in simulation during the current quantum of simulation time, then the method decreases the quantum length. The method is repeated until simulation of execution of the nodes has finished. 
     A system according to an embodiment of the present disclosure is for simulating substantially parallel execution of nodes interconnected by a network. The system includes hardware and one or more simulation components implemented within the hardware. The simulation components simulate substantially parallel execution of the nodes over a number of quanta of simulation time having a quantum length. Simulation of execution within each quantum can result in simulation of inter-node data packets being transmitted over the network. Simulation of execution of the nodes is further synchronized in-between successive quanta. 
     The simulation components also dynamically modify the quantum length in-between successive quanta, such that a likelihood that a straggler inter-node data packet results during simulation is reduced while permitting simulation to be quickly completed. A straggler inter-node data packet is an inter-node data packet transmitted in simulation from a first node to a second node and that arrives at the second node later than when the straggler inter-node data packet was scheduled to arrive at the second node. 
     A computer-readable medium according to an embodiment of the present disclosure has one or more computer programs stored thereon that are executable by one or more processors to perform a method. The method is for dynamically modifying a quantum length of a number of quanta of simulation time in which substantially parallel execution of nodes interconnected by a network are simulated. Simulation of execution within each quantum can result in simulation of inter-node data packets being transmitted over the network. Simulation of execution of the nodes is synchronized in-between successive quanta. 
     After each quantum of simulation time, the method performs the following. Where no inter-node data packets were transmitted in simulation during the quantum of simulation time, the method increases the quantum length of a next quantum of simulation time such that the quantum length slowly increases over successive increases. Where one or more inter-node data packets were transmitted in simulation during the quantum of simulation time, the method decreases the quantum length of the next quantum of simulation time such that the quantum length quickly decreases over successive decreases. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIGS. 1A and 1B  are diagrams of different multiple-node computing systems that can have their execution simulated, according to varying embodiments of the present disclosure. 
         FIG. 2  is a diagram depicting how substantially parallel execution of nodes of a multiple-node computing system can be simulated using a number of quanta of simulation time, according to an embodiment of the present disclosure. 
         FIGS. 3A ,  3 B,  3 C, and  3 D are diagrams depicting how transmission of inter-node data packets can occur in simulation when using a number of quanta of simulation time in simulating execution of a multiple-node computing system, according to varying embodiments of the present disclosure. 
         FIG. 4  is a diagram depicting how straggler inter-node data packets can be avoided when using a number of quanta of simulation time in simulating execution of a multiple-node computing system, according to an embodiment of the present disclosure. 
         FIGS. 5A and 5B  are diagrams depicting how using a number of quanta of simulation time having different quantum lengths can result in increasing or decreasing of simulation completion time when simulating execution of a multiple-node computing system, according to varying embodiments of the present disclosure. 
         FIGS. 6A and 6B  are flowcharts of a method for simulating substantially parallel execution of nodes of a multiple-node computing system using a number of quanta of simulation time in which quantum length is dynamically modified, according to an embodiment of the present disclosure. 
         FIG. 7  is a diagram of a representative system for simulating substantially parallel execution of nodes of a multiple-node computing system, according to an embodiment of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION OF THE DRAWINGS 
       FIG. 1A  shows a multiple-processor computing system  100  that can have its execution simulated, according to an embodiment of the present disclosure. 
     The computing system  100  includes a number of discrete computing device nodes  102 A,  102 B, . . . ,  102 N, which are collectively referred to as the computing device nodes  102 . Each of the nodes  102  is a discrete computing device, such as a server computing device in one embodiment. The nodes  102  may also be referred to as clusters. 
     The computing device node  102 A is depicted in detail in  FIG. 1A  as representative of all the nodes  102 . The computing device node  102 A includes one or more processors  106 , memory  108 , and/or one or more storage devices  110 , such as hard disk drives and the like. The computing device node  102 A may include other components, in addition to and/or in lieu of those depicted in  FIG. 1 , such as peripheral devices, networking devices, and so on. 
     The computing device nodes  102  are interconnected to one another via a network  104 . The network  104  may be a wired and/or a wireless network. For instance, the network  104  may be or include the Internet, intranets, extranets, local-area networks (LAN&#39;s), wide-area networks (WAN&#39;s), as well as other types of networks. 
       FIG. 1B  shows an integrated circuit (IC)  150  that is another type of multiple-processor computing system, according to an embodiment of the present disclosure. The IC  150  can be considered a chip multiprocessor (CMP) in one embodiment. The IC  150  includes a number of nodes  152 A,  152 B, . . . ,  152 N, collectively referred to as the nodes  152 , and a shared memory network  154  shared by all the nodes  152 . The nodes  152  may also be referred to as clusters. The shared memory network  154  may be a level-three (L3) cache in one embodiment of the present disclosure. 
     The node  152 A is depicted in detail in  FIG. 1B  as representative of all the nodes  152 . The node  152 A is depicted in the embodiment of  FIG. 1B  as including a number of processors  156 A,  156 B, . . . ,  156 M, collectively referred to as the processors  156 . While there are multiple processors  156  depicted in  FIG. 1B , in another embodiment, the node  152 A may just have a single processor  156 . 
     In one embodiment, the processors  156  have corresponding memories  158 A,  158 B, . . . ,  158 M, collectively referred to as the memories  158 . The memories  158  are not shared among the processors  156 . For example, the memory  158 A is private memory for the processor  156 A, and is not shared with other of the processors  156  of the node  152 A, nor with other processors of other nodes. The memories  158  may be a level-one (L1) cache in one embodiment of the present disclosure. 
     The node  152 A also includes memory  160  that is shared among all the processors  156  of the node  152 A. However, the memory  160  is not shared with any other node. That is, the memory  160  is shared just by the processors  156  of the node  152 A, and not with any processor of any other node. Therefore, for a collection of nodes  152 , the processors  156  of each of the nodes  152  share corresponding memory  160  that is different than the corresponding memory  160  shared by the processor of each other of the nodes  152 . The memory  160  may be a level-two (L2) cache in one embodiment of the present disclosure. 
     The nodes of the multiple-node computing systems of  FIGS. 1A and 113  can execute in parallel with one another. However, at times, the execution of the nodes has to be synchronized. For example, if a data packet, such as a memory request like a read or write request, or another type of data packet, is transmitted from one node to another node over the network interconnecting the nodes, execution may have to be synchronized based on the contents of such an inter-node data packet. It can be presumed that the nodes execute in parallel without having to be synchronized more often than not. That is, for most of the execution time of a node, the node does not receive inter-node data packets from other nodes that may require synchronization. Such execution of the nodes is referred to herein as substantially parallel execution of the nodes. 
       FIG. 2  shows how substantially parallel execution of the nodes of a multiple-node computing system can be simulated using quanta, according to an embodiment of the present disclosure. For convenience, two nodes  202 A and  202 B, collectively referred to as the nodes  202 , have their substantially parallel execution being simulated. The substantially parallel execution of the nodes  202  is simulated over a number of discrete quanta of simulation time  206 A,  206 B,  206 C, . . . ,  206 L, collectively referred to as the quanta  206 . The execution of the nodes  202 A and  202 B occurs beginning at the quantum  206 A and ends at the quantum  206 L, such that time elapses downward in  FIG. 2 , as indicated by the arrow  204 . 
     Within each quantum of simulation time  206 , execution of the nodes  202  is simulated. Between successive quanta  206 , simulation of execution of the nodes  202  is then synchronized. Within a given quantum  206 , simulation of execution of one node  202  may be completed before the simulation of execution of the other node  202  is completed. The solid arrow under a node  202  within a given quantum  206  corresponds to the time it takes to simulate execution of the node  202  within that quantum  206 . If simulation time finishes before the quantum  206  in question elapses, a dotted line denotes the length of time after simulation of execution of the node  202  has finished until the end of the quantum  206 . 
     For example, as to the quantum of simulation time  206 B, simulation of execution of the node  202 A takes the entire quantum  206 B, as indicated by the solid arrow  208 A, whereas simulation of execution of the node  202 B takes just an initial portion of the quantum  206 B, as indicated by the solid arrow  208 B and the dotted line  210 . By comparison, in the quantum of simulation time  206 A, simulation of execution of the node  202 A does not take the entire quantum  206 A, whereas simulation of execution of the node  202 B does, as is the case in the quantum of simulation time  206 L. As to the quantum of simulation time  206 C, simulation of execution of both nodes  202  takes the entire quantum  206 C. 
     The length of time of a quantum of simulation time  206  is dynamic, or variable, and is modified as is described later in the detailed description. The quanta  206  have corresponding quantum lengths of times  212 A,  212 B,  212 C, . . . ,  212 L, collectively referred to as the quantum lengths of time  212 . Thus, the quantum length  212 A for the quantum  206 A is less than the quantum length  212 B for the quantum  206 B, but is greater than the quantum lengths  212 C and  212 L for the quanta  206 C and  206 L. 
     Dividing the simulation of execution of the nodes  202  into quanta of simulation time  206  permits the substantially parallel execution of the nodes  202  to be simulated in a relatively efficient manner. Furthermore, such division into quanta  206  permits inter-node data packets that may be sent between the nodes  202  and that can require synchronization of simulation of execution of the nodes  202  to be taken into account. In particular, the quantum lengths  212  of the quanta  206  can be dynamically modified to ensure that in most cases, proper synchronization of simulation of substantially parallel execution of the nodes  202  can occur. For instance, what is attempted to be avoided is for an inter-node data packet to arrive in simulation at a given node at time t A , when the node in question already has its execution being simulated at time t B  greater than t A . (It is noted that the phrase “in simulation” is used herein to indicate that transmission of inter-node data packets and execution of the nodes are not actually occurring in reality, but rather are being simulated.) 
       FIGS. 3A ,  3 B,  3 C, and  3 D show how transmission of inter-node data packets can occur in simulation when using quanta of simulation time in simulating substantially parallel execution of the nodes of a multiple-node computing system, according to different embodiments of the present disclosure. In each of these figures, time proceeds downward for the given quantum of simulation time. This is indicated by the arrow  204 . 
     In  FIG. 3A , simulation of execution of the node  202 A within the quantum of simulation time  302  occurs at about the same rate as simulation of execution of the node  202 B within the quantum  302  does. This is indicated by the solid arrow  304 A, corresponding to the execution simulation time of the node  202 A within the quantum  302 , being substantially equal in length to the solid arrow  304 B, corresponding to the execution simulation time of the node  202 B within the quantum  302 . The arrows  304 A and  304 B can be collectively referred to as the arrows  304 . 
     An inter-node data packet  306  is sent from the node  202 A at execution simulation time point  2  and is received by the node  202 B at execution simulation time point  4 . The inter-node data packet  306  ideally has a latency of two, and thus  FIG. 3A  reflects this ideal situation occurring. It takes two units of execution time for the node  202 B to process the data packet  306 , and a responsive inter-node data packet  308  is sent back to the node  202 A at execution simulation time point  6 , which is received by the node  202 A at execution simulation time point  8 . The inter-node data packet  308  also ideally has a latency of two, and this is reflected in  FIG. 3A . 
     Thus,  FIG. 3A  reflects the ideal situation in which the node  202 A is at a current execution simulation time point of 8 when the inter-node data packet  308  is supposed to arrive at the node  202 A, taking into account the expected latency time of both data packets  306  and  308  and the expected processing time of the data packet  306  at the node  202 B. Stated another way, in  FIG. 3A  the node  202 A is at a current execution simulation time point of 8 that is equal to a target execution simulation time point of 8 when the inter-node data packet  308  is supposed to arrive at the node  202 A, taking into account the expected latency times of the data packets  306  and  308  and the expected processing time of the data packet  306  at the node  202 B. In this ideal case, then, the inter-node data packet  308  is transmitted to the node  202 A in simulation as soon as the node  202 B has finished processing the data packet  306  at execution simulation time point  6 , without delay and taking into account the latency of the transmission of the data packet  308 . 
     In  FIG. 3B , simulation of execution of the node  202 A within the quantum of simulation time  312  occurs more slowly as compared to the simulation of execution of the node  202 B within the quantum  312  does. This is indicated by the solid arrow  314 A, corresponding to the execution simulation time of the node  202 A within the quantum  312 , being longer than the solid arrow  314 B, corresponding to the execution simulation time of the node  202 B within the quantum  312 . The arrows  314 A and  314 B can be collectively referred to as the arrows  314 . 
     An inter-node data packet  316  is sent from the node  202 A at execution simulation time point  2 . Although the inter-node data packet  316  ideally has a latency of two, because the node  202 B has its execution being simulated more quickly, the node  202 B does not receive the data packet  316  until execution simulation time point  5 . It takes two units of execution time for the node  202 E 3  to process the data packet  316 , and a responsive inter-node data packet  318  is sent back to the node  202 A at execution simulation time point  7 . As before, the data packet  318  ideally has a latency of two, which means that the node  202 A should receive the data packet  318  at execution simulation time point  9 . However, because the node  202 A has its execution being simulated more slowly, it may actually receive the data packet  318  when it is at execution simulation time point  5 . Therefore, the simulation can synchronize this substantially parallel execution of the nodes  202  by simply delaying receipt of the inter-node data packet  318  by the node  202 A until the node  202 A is at execution simulation time point  9 . 
     Thus,  FIG. 3B  reflects the situation in which the node  202 A is at a current execution simulation time point of 5 when the inter-node data packet  318  is supposed to arrive at the node  202 A at an execution simulation time point of 9. Stated another way, in  FIG. 3B  the node  202 A is at a current execution simulation time point (of 5) that is less than a target execution simulation time point (of 9) when the inter-node data packet  318  is supposed to arrive at the node  202 A. This case is easily rectified by delaying transmission of the inter-node data packet  318  to the node  202 A in simulation when the current execution simulation time point of the node  202 A becomes equal to the target simulation time point, during the quantum  312 . 
     It is noted that a slight modification of the situation of  FIG. 3B  can occur where the target execution simulation time point at which the inter-node data packet  318  is supposed to arrive at the node  202 A in simulation is not during the current quantum  312 . For instance, the quantum may have a quantum length of time of 10. If the target execution simulation time point at which the data packet  318  is supposed to arrive at the node  202 A in simulation is 12, then this means that transmission of the data packet  318  to the node  202 A in simulation is again delayed. However, unlike in the case described in the previous paragraph, transmission of the data packet  318  to the node  202 A in simulation does not occur within the quantum  322 , but rather occurs at an execution simulation time point of 2 within the next quantum. Such an execution simulation time point corresponds to a target execution simulation time point of 12, where the quantum length of the quantum  322  is 10, and adding 2 to this length yields 12. 
     In  FIG. 3C , simulation of execution of the node  202 A within the quantum of simulation time  322  occurs slightly more quickly as compared to the simulation of execution of the node  202 B within the quantum  322  does. This is indicated by the solid arrow  324 A, corresponding to the execution simulation time of the node  202 A within the quantum  322 , being slightly shorter than the solid arrow  324 E 3 , corresponding to the execution simulation time of the node  202 B within the quantum  322 . The arrows  324 A and  324 B can be collectively referred to as the arrows  324 . 
     An inter-node data packet  326  is sent from the node  202 A at execution simulation time point  2 . Although the inter-node data packet  326  ideally has a latency of two, because the node  202 B has its execution being simulated more slowly, the node  202 B receives the data packet  326  earlier than expected, at execution simulation time point  3 . It takes two units of execution time for the node  202 B to process the data packet  326 , and a responsive inter-node data packet  328  is sent back to the node  202 A at execution simulation time point  5 . As before, the data packet  328  ideally has a latency of two, which means that the node  202 A should receive the data packet  328  at execution simulation time point  7 . However, because the node  202 A has its execution being simulated more quickly, it may actually receive the data packet  328  when it is at execution simulation time point  9 . 
     The simulation cannot therefore synchronize this substantially parallel execution of the nodes  202 , because the execution simulation time point  7  at which the node  202 A should have received the inter-node data packet  328  has already passed, and it can be undesirable to “roll back” simulation of execution of the node  202 A. Therefore, the data packet  328  is simply transmitted to the node  202 A at execution simulation time point  9 , where the simulation of execution of the node  202 A has not yet finished for the quantum of simulation time  322 . As such, the data packet  328  is considered a straggler data packet, in that it is transmitted to the node  202 A after the data packet  328  was supposed to arrive at the node  202 A. While transmitting the data packet  328  to the node  202 A at a later point in time than it should have been can deleteriously affect execution simulation accuracy, embodiments of the present disclosure minimize the occurrence of straggler data packets, as is described in more detail later in the detailed description. 
     Thus,  FIG. 3C  reflects the situation in which the node  202 A is at a current execution simulation time point of  9  when the inter-node data packet  328  is supposed to arrive at the node  202 A at an execution simulation time point of  7 . Stated another way, in  FIG. 3C  the node  202 A is at a current execution simulation time point (of  9 ) that is greater than a target execution simulation time point (of  7 ) when the inter-node data packet  328  is supposed to arrive at the node  202 A. However, simulation of execution of the node  202 A is still occurring, such that the data packet  328  is still transmitted to the node  202 A in simulation during the quantum of simulation time  322 . 
     In  FIG. 3D , simulation of execution of the node  202 A within the quantum of simulation time  332  occurs significantly more quickly as compared to the simulation of execution of the node  202 B within the quantum  332  does. This is indicated by the solid arrow  334 A, corresponding to the execution simulation time of the node  202 A within the quantum  332 , being significantly shorter than the solid arrow  334 B, corresponding to the execution simulation time of the node  202 B within the quantum  332 . The arrows  334 A and  334 B can be collectively referred to as the arrows  334 . 
     An inter-node data packet  336  is sent from the node  202 A at execution simulation time point  2 . Although the inter-node data packet  336  ideally has a latency of two, because the node  202 B has its execution being simulated more slowly, the node  202 B receives the data packet  336  earlier than expected, at execution simulation time point  3 . It takes two units of execution time for the node  202 B to process the data packet  336 , and a responsive inter-node data packet  338  is sent back to the node  202 A at execution simulation time point  5 . As before, the data packet  338  has a latency of two ideally, which means that the node  202 A should receive the data packet  338  at execution simulation time point  7 . However, because the node  202 A has its execution being simulated much more quickly, in  FIG. 3D  its execution simulation has already been completed for the quantum  332  by the time the node  202 B transmits the data packet  338 . 
     The simulation cannot therefore synchronize this substantially parallel execution of the nodes  202 , because in  FIG. 3D , as in  FIG. 3C , the execution simulation time point  7  at which the node  202 A should have received the inter-node data packet  338  has already passed, and it can be undesirable to “roll back” simulation of execution of the node  202 A. Furthermore, in  FIG. 3D , but unlike as in  FIG. 3C , the data packet  338  cannot simply be transmitted to the node  202 A during the quantum of simulation time  332 , because the simulation of execution of the node  202 A has already been finished for the quantum  332 . 
     Rather, the data packet  338  is scheduled for transmission to the node  202 A at the beginning of the next quantum of simulation time immediately after the quantum  332 . As such, in  FIG. 3D , as in  FIG. 3C , the data packet  338  is considered a straggler data packet, in that it is transmitted to the node  202 A after the data packet  338  was supposed to arrive at the node  202 A. 
     Thus,  FIG. 3D  reflects the situation in which the simulation of execution of the node  202 A has already been completed, or has finished, for the current quantum of simulation time  332  when the inter-node data packet  328  is supposed to arrive at the node  202 A at an execution simulation time point of  7 . Stated another way, in  FIG. 3D  the node  202 A has its execution simulation already finished, or completed, at the target execution simulation time point (of  7 ) when the inter-node data packet  338  is supposed to arrive at the node  202 A. Although simulation of execution of the node  202 A is not still occurring within the current quantum  332 , the data packet  328  is still transmitted to the node  202 A in simulation, but during the next quantum of simulation time after the current quantum  332 . 
     A conservative approach to preventing straggler inter-node data packets from occurring is to set the quantum length of time of each quantum of simulation time to a value less than the latency of the inter-node data packets (i.e., less than the time it takes to transmit a data packet from one node to another node). Doing this guarantees that no inter-node data packet will be able to be transmitted in simulation from one node to another node within a given quantum, but rather ensures that transmission of any inter-node data packet will always occur over two quanta in simulation. As such, between the two quanta, the simulation of execution of the receiving node of the data packet can be synchronized so that it receives the data packet at the correct execution simulation time point. 
       FIG. 4  illustratively depicts this conservative approach to preventing straggler inter-node data packets from occurring, according to an embodiment of the present disclosure. As before, there are two nodes  202 , where time proceeds downward as indicated by the arrow  204 . There are two quanta of simulation time  402 A and  402 B, collectively referred to as the quanta  402 , which have quantum lengths of time  404 A and  404 B, collectively referred to as quantum lengths  404 . Over the two quanta  402 , the node  202 A has its execution simulated as indicated by the solid arrows  406 A and  406 B, collectively referred to as the arrows  406 , and the node  202 B has its execution simulated as indicated by the solid arrows  408 A and  408 B, collectively referred to as the arrows  408 . 
     In  FIG. 4 , the quantum lengths  404  of the quanta  402  are equal to three time units, while the latency of an inter-node data packet  410  sent in simulation from the node  202 B to the node  202 A is four time units. This means that no matter when the node  202 B sends the data packet  410  within the quantum  402 A, the target simulation time point when the data packet  410  is to arrive at the node  202 A is guaranteed never to be within the quantum  402 A, but rather is guaranteed to be within the quantum  402 B. For example, even if the node  202 B sends the inter-node data packet  410  immediately when the quantum  402 A starts, the quantum  402 A will be over at the third time unit overall, but the data packet  410  will not be scheduled for delivery at the node  202 A until the fourth time unit overall, within the quantum  402 B. 
     Furthermore, the node  202 A can have its simulation of execution synchronized between the quanta  402  so that the simulation of execution of the node  202 A within the quantum  402 B takes into account the execution simulation time point when the node  202 A is to receive the inter-node data packet  410 . For example, if the inter-node data packet  410  is sent from node  202 B in simulation at the second time unit within the quantum  402 A, this means that the data packet  410  will arrive in simulation at the node  202 A at the second time unit within the quantum  402 B (i.e., the fourth time unit overall). This is because the packet  410  has a latency of four time units and the quantum lengths  404  of the quanta  402  are both equal to three time units. 
     Between the quanta  402 , the simulation of execution the node  202 A is made aware that it will be receiving the data packet  410  at the second time unit within the quantum  402 B. Therefore, when the simulation of execution of the node  202 A has proceeded to the second time unit with the quantum  402 B, if the execution simulation of the node  202 A has not yet received the data packet  410 , it can wait for the data packet  410  to arrive. As such, the synchronization of execution simulation of the nodes  202  that occurs between the quanta  402  can ensure that straggler inter-node data packets are prevented, by communicating to the nodes  202  which data packets they should expect to receive in simulation in the next quantum, and when. 
     The conservative approach for simulating substantially parallel execution of the nodes of a multiple-node computing system is thus useful in ensuring that straggler inter-node data packets are prevented. In the conservative approach, the quantum length of time of each quantum of simulation time is set to less than the smallest expected latency of any inter-node data packet that may be transmitted in simulation. However, as has been noted above, embodiments of the present disclosure dynamically modify the quantum lengths of the quanta. This is because statically setting the quantum length of each quantum at less than the smallest expected latency of any inter-node data packet unduly increases total execution simulation time. 
     For instance,  FIGS. 5A and 5B  show the same simulation of execution of the two nodes  202 , according to an embodiment of the present disclosure. In both  FIGS. 5A and 5B , time again proceeds downward as indicated by the arrows  204 . In  FIG. 5A , there are four quanta of simulation time  502 A,  502 B,  502 C, and  502 D, collectively referred to as the quanta  502 , whereas in  FIG. 5B , there is one quantum of simulation time  552 .  FIGS. 5A and 5B  are drawn to scale, meaning that the quantum length of time of each quantum  502  in  FIG. 5A  is much shorter than the quantum length of time of the quantum  552  in  FIG. 5B . 
     In  FIG. 5A , simulation of execution of the nodes  202  proceeds as follows. Over the quanta  502 , the node  202 A is simulated as indicated by arrows  506 A,  506 B,  506 C, and  506 D, collectively referred to as the arrows  506 , and the node  202 B is simulated as indicated by arrows  508 A,  508 B,  508 C, and  508 D, collectively referred to as the arrows  508 . Dotted lines  510 A and  510 B, collectively referred to as the dotted lines  510 , indicate when the simulation of execution of the node  202 A has finished within the quanta  502  such that the simulation is waiting for the next quantum to occur. Likewise, dotted lines  512 A and  512 B, collectively referred to as the dotted lines  512 , indicate when the simulation of the execution of the node  202 B has finished within the quanta  502  such that the simulation is waiting for the next quantum to occur. 
     Furthermore, gaps  504 A,  504 B, and  504 C, collectively referred to as the gaps  504 , between successive quanta  502  correspond to the overhead (in time) needed to synchronize the nodes  202  before the next quantum begins. Such synchronization can include determining and informing the execution simulation of the nodes  202  the quantum length of the next quantum of simulation time, which node-executable instructions are to have their execution simulated in the next quantum, which inter-node data packets to expect at what simulation time points in the next quantum, and so on. The total execution simulation time  514  in  FIG. 5A  is thus the total of the quantum lengths of time of the quanta  502 , plus the time delays represented by the gaps  504 . 
     By comparison, in  FIG. 5B , simulation of the nodes  202  proceeds as follows. Over the single quantum  552 , the node  202 A is simulated as indicated by the arrow  554 A, while the node  202 B is simulated as indicated by the arrow  554 B, where the arrows  554 A and  554 B are collectively referred to as the arrows  554 . The arrow  554 A has a length equal to the total length of all the arrows  506  of  FIG. 5A , whereas the arrow  554 B has a length equal to the total length of all the arrows  508  of  FIG. 5A . The arrow  554 B is slightly shorter than the arrow  554 A, meaning that there is a period of time in which the simulation of execution of the node  202 B has finished within the quantum  552 , as indicated by the dotted line  556 . 
     The total simulation time  558  in  FIG. 5B  is thus simply equal to the length of the quantum  552 . The total simulation time  558  in  FIG. 5B  is much shorter than the total simulation time  514  in  FIG. 5A , because of two factors. First, there is no inter-quanta overhead within the single quantum  552  in  FIG. 5B  as compared to within the quanta  502  in  FIG. 5A , where such overhead is represented by the gaps  504  in  FIG. 5A . Second, in the quanta  502 A in  FIG. 5A , the nodes  202  have to at times wait for the next quantum to occur before execution simulation can continue (or end), as specifically represented by the dotted lines  510  and  512 . This also contributes to the total simulation time  514  in  FIG. 5A  being longer than the total simulation time  558  in  FIG. 5B . 
     Therefore, embodiments of the present disclosure attempt to balance two competing goals. First, straggler inter-node data packets are to be avoided, which militates in favor of shorter quantum lengths of time of the quanta of simulation time. Second, however, total simulation time should be as small as possible to ensure execution simulation performance, which militates in favor of longer quantum lengths of time of the quanta of simulation time. How one embodiment balances these two competing goals is now described in detail. 
       FIGS. 6A and 6B  show a method  600  for simulating substantially parallel execution of nodes of a multiple-node computing system using a number of quanta of simulation time in which quantum lengths of time of the quanta are dynamically modified, according to an embodiment of the present disclosure. Referring first to  FIG. 6A , the quantum length for the first quantum of simulation time is initially set to a minimum value ( 602 ). For instance, the minimum value may be the minimum latency time value of transmission of an inter-node data packet between two nodes, to ensure that at the beginning of the method  600 , there are no straggler data packets. For the first iteration of the method  600 , the first quantum is the current quantum of simulation time. 
     Substantially parallel execution of the nodes is simulated during (i.e., for) the current quantum of simulation time ( 604 ). As has been noted above, such execution simulation can include at times the simulation of the transmission of an inter-node data packet from a first node to a second node ( 606 ). In such instance, there are five different cases that can occur, as has been described above in relation to  FIGS. 3A-3C . 
     First, the second node may be at a current simulation time point that is less than the target simulation time point when the data packet is to arrive at the second node, and the target simulation time point occurs within the current quantum of simulation time ( 608 ). In such instance, the data packet is transmitted in simulation to the second node (i.e., the data packet is to arrive at the second node in simulation) when the current simulation time point of the second node becomes equal to the target simulation time point, within the current quantum. This case has been described above in relation to  FIG. 3B . 
     Similarly, second, the second node may be at a current simulation time point that is less than the target simulation time point when the data packet is to arrive at the second node, but the target simulation time point occurs after the current quantum of simulation time has ended ( 610 ). In such instance, the data packet is transmitted in simulation to the second node (i.e., the data packet is to arrive at the second node in simulation) when the current simulation time point of the second node becomes equal to the target simulation time point, as before, but within the next quantum. This case has also been described above in relation to  FIG. 3B . 
     Third, the second node may be at a current simulation time point that is exactly equal to the target simulation time point when the data packet is to arrive at the second node ( 612 ). In such instance, the data packet is transmitted in simulation to the second node (i.e., the data packet arrives at the second node in simulation) without delay. This case has been described above in relation to  FIG. 3A . 
     Fourth, the second node may be at a current simulation time point that is greater than the target simulation time point when the data packet is to arrive at the second node, and simulation of execution of the second node has not yet finished for the current quantum ( 614 ). In such instance, the data packet is transmitted in simulation to the second node (i.e., the data packet is to arrive at the second node in simulation) without delay, but the data packet is a straggler data packet. This case has been described above in relation to  FIG. 3C . 
     Fifth, simulation of execution of the second node may have already finished for the current quantum at the target simulation time point when the data packet is to arrive at the second node ( 616 ). In such instance, the data packet is transmitted in simulation to the second node (i.e., the data packet is to arrive at the second node in simulation) at the beginning of the next quantum of simulation time, but the data packet here, too, is a straggler data packet. This case has been described above in relation to  FIG. 3D . 
     Referring next to  FIG. 6B , when the current quantum of simulation time has finished ( 618 ), simulation of execution of the nodes is synchronized for the next quantum of simulation time ( 620 ), if any. As has been noted above, such synchronization can include which node-executable instructions are to have their execution simulated in the next quantum, which inter-node data packets to expect at what simulation time points in the next quantum, and so on. Such synchronization can also include informing the execution simulation of the nodes the quantum length of the next quantum of simulation time, as is determined after parts  622  and  628  are performed, which are now described. 
     First, if no inter-node data packets were transmitted in simulation during the most recent (i.e., current) quantum of simulation time, then the quantum length of the next quantum of simulation time is increased as compared to the current quantum ( 622 ). In one embodiment, the quantum length increases slowly over successive such increases. Increasing the quantum length aids the performance of the simulation, since the smaller the quantum length is, the more quanta that will be needed to finish the simulation. That is, increasing the quantum length permits the simulation to be performed as quickly as posible. 
     At the same time, increasing the quantum length slowly helps reduce the likelihood that straggler inter-node data packets result during simulation. That is, if the quantum length is quickly increased, then the likelihood that a straggler inter-node data packet will result during such a relatively long quantum is increased. Therefore, in one embodiment of the present disclosure, the method  600  is conservative in increasing the quantum length when no inter-node data packet was transmitted in the most recent quantum of simulation time. 
     In one embodiment, the quantum length is increased as follows. The current quantum length (i.e., the quantum length of the current quantum) is multiplied by a predetermined increase factor ( 624 ). In one embodiment, this increase factor may be between 101% to 110%, which means that each time the quantum length is increased, it increases by one to ten percent. However, there is a predetermined maximum quantum length. Therefore, if the quantum length becomes greater than this maximum quantum length, it is set equal to the maximum quantum length ( 626 ). 
     Second, if one or more inter-node data packets were transmitted in simulation during the most recent (i.e., current) quantum of simulation time, then the quantum length of the next quantum of simulation time is decreased as compared to the current quantum ( 628 ). In one embodiment, the quantum length decreases quickly over successive such decreases. Decreasing the quantum length, especially quickly, reduces the likelihood that straggler inter-node data packets result during simulation. As soon as an inter-node data packet is transmitted, it is presumed, in other words, that other data packets are likely to follow in successive quanta, such that to avoid straggler data packets, the quantum length is quickly decreased. 
     In one embodiment, the quantum length is decreased as follows. The current quantum length (i.e., the quantum length of the current quantum) is divided by a predetermined decrease factor ( 630 ). In one embodiment, this decrease factor may be between a cube root and a square root of the maximum value for the quantum length. However, there is a predetermined minimum quantum length. Therefore, if the quantum length becomes less than this minimum quantum length, it is set equal to the minimum quantum length ( 632 ). 
     The method  600  is then repeated at part  604  of  FIG. 6A  for the next quantum of simulation time (i.e., where the next quantum becomes the new current quantum of simulation time), until simulation of execution of the nodes has finished ( 634 ). The method  600  thus dynamically modifies quantum length over successive quanta of simulation time, based on whether any inter-node data packets were transmitted in the immediately prior quantum. As inter-node data packets are transmitted over given quanta, the quantum length is quickly decreased, to substantially reduce the likelihood that straggler data packets will result. As given quanta occur in which no inter-node data packets are transmitted, the quantum length is slowly increased, to conservatively improve performance of the entire simulation while aiding the reduction in the likelihood that straggler data packets will result. 
     This embodiment of the present disclosure can be conceptualized by a speed bump metaphor. When a motor vehicle encounters a speed bump on the roadway, its driver quickly slows the vehicle down. Once the speed bump has passed, the driver slowly increases the speed of the vehicle, especially if the driver is uncertain as to whether there are more impending speed bumps. In the same way, when an inter-node data packet is encountered, the method  600  can quickly decrease the quantum length to prevent the likelihood that straggler data packets will occur. When no inter-node data packets are encountered, the method  600  can then increase the quantum length, to increase simulation performance, but slowly, because it may not be known whether there are more impending inter-node data packets that will be encountered. 
     This embodiment of the present disclosure can also be considered as leveraging how inter-node data packets may be transmitted in simulation of execution. In particular, typically when one inter-node data packet is transmitted, this event portends that subsequent inter-node data packets are likely to be transmitted soon. That is, such data packets may typically be transmitted in “bunches,” interspersed by longer periods of time in which no data packets are transmitted. Therefore, when the first data packet is transmitted, it is advantageous to quickly decrease quantum length, since more data packets are likely to follow. Likewise, it is advantageous to slowly increase quantum length when no data packets are transmitted, because it may not be able to be known when another data packet will be transmitted in simulation, and in any case, performance will steadily increase due to the expected relatively long period of time in which no data packets are transmitted. 
     In conclusion,  FIG. 7  shows a system  700 , according to an embodiment of the present disclosure. The system  700  includes hardware  702  and one or more simulation components  704 . The hardware  702  may include processors, memory, storage devices, network devices, and/or other types of hardware, as can be appreciated by those of ordinary skill within the art. The simulation component  704  is implemented within the hardware  702 . For instance, the simulation component  704  may be software that is programmed to run on the hardware  702 , such as a simulation computer program that runs on the hardware  702  via an operating system, as can be appreciated by those of ordinary skill within the art. As another example, the hardware  702  may include computer-readable media such as hard disk drives and semiconductor memory. In such instance, the hardware  702  can be considered as storing computer programs that are executable by processors to implement the simulation component  704 . 
     The simulation component  704  performs the simulation that has been described in relation to the method  600  of  FIGS. 6A and 6B . That is, the simulation component  704  can perform the method  600  that has been described. For instance, the simulation component  704  simulates substantially parallel execution of nodes over a number of quanta of simulation time that have a quantum length. Simulation of execution within each quantum can result in simulation of inter-node data packets being transmitted over a network interconnecting the nodes. Simulation of execution of the nodes is synchronized in-between successive quanta. Simulation of execution of each node within a given quantum can be performed by using a simulator like the simulator SimNow™, available from Advanced Micro Devices, Inc., of Sunnyvale, Calif. 
     Furthermore, the simulation component  704  dynamically modifies the quantum length in-between successive quanta such that the likelihood that a straggler inter-node data packet may result during simulation is reduced. This can be achieved by quickly decreasing the quantum length of the next quantum of simulation time when an inter-node data packet is encountered in the current quantum of simulation time, as has been described. At the same time, dynamic modification of the quantum length permits the simulation to be completed relatively quickly. This can be achieved by slowly increasing the quantum length of the next quantum of simulation time when an inter-node data packet is not encountered in the current quantum of simulation time, as has also been described.