In lecture, this slide showed a single packet being sent from the source to the destination. While the time taken for each individual transfer is the same as the previous slide, once the header is sent to the next node, we can begin copying to the next node before the original transfer is even complete. For instance, the tail of the packet might be in the first node, the middle 50% of the packet in the second node, and the head of the packet in the third node.
While we use more links at a time than the previous slide, we complete the entire transmission in only 8 time steps since (in this example) we only need the first 50% of the packet before we can begin copying to the next node. Thus at time step 5, the first 25% of the packet is already at the destination.
In the high contention case, since we can't reserve future links, we will probably just devolve into the previous slide's Store-and-Forward model.
This comment was marked helpful 1 times.
monster
Here the latency of store-and-forward is 4n, and the latency of cut-through-flow is ~2n where n is the number of links from source to the destination. If the data is m times bigger than the header, the latency of store-and-forward is O(mn) however the latency of cut-through-flow is O(n). Therefore the packet is larger, we saved more latency in cut-through-flow rather than store-and-forward.
This comment was marked helpful 0 times.
raphaelk
Question: From the lecture video, first two packets needed to be in a switch for the first switch to move to a next switch. For example, it went
4 - 0 - 0 - 0
3 - 1 - 0 - 0
2 - 2 - 0 - 0
1 - 2 - 1 - 0
but if the header packet reaches the second switch, why can't it jump right into the third switch, so it goes like
4 - 0 - 0 - 0
3 - 1 - 0 - 0
2 - 1 - 1 - 0
1 - 1 - 1 - 1
Is it due to the latency reserving the link so the header had to wait for 1 time step or because the header has size of 2 packets in this example? It seems like Wormhole flow control is doing it.
This comment was marked helpful 0 times.
hh
@raphaelk In terms of terminology, the whole thing is just one packet broken up, not four packets. In this example, the wait is because the header has a size of two pieces (don't know if they would be flits since it's a continuous flow of data as opposed to breaking up the packets into specific pieces).
This comment was marked helpful 0 times.
Arnie
Under high contention, the output link is frequently blocked, so the packet coming in is stored in a packet buffer until it can be sent out. Thus if the link is continually blocked, cut-through reduces to store-and-forward.
In lecture, this slide showed a single packet being sent from the source to the destination. While the time taken for each individual transfer is the same as the previous slide, once the header is sent to the next node, we can begin copying to the next node before the original transfer is even complete. For instance, the tail of the packet might be in the first node, the middle 50% of the packet in the second node, and the head of the packet in the third node.
While we use more links at a time than the previous slide, we complete the entire transmission in only 8 time steps since (in this example) we only need the first 50% of the packet before we can begin copying to the next node. Thus at time step 5, the first 25% of the packet is already at the destination.
In the high contention case, since we can't reserve future links, we will probably just devolve into the previous slide's Store-and-Forward model.
This comment was marked helpful 1 times.
Here the latency of store-and-forward is 4n, and the latency of cut-through-flow is ~2n where n is the number of links from source to the destination. If the data is m times bigger than the header, the latency of store-and-forward is O(mn) however the latency of cut-through-flow is O(n). Therefore the packet is larger, we saved more latency in cut-through-flow rather than store-and-forward.
This comment was marked helpful 0 times.
Question: From the lecture video, first two packets needed to be in a switch for the first switch to move to a next switch. For example, it went
4 - 0 - 0 - 0
3 - 1 - 0 - 0
2 - 2 - 0 - 0
1 - 2 - 1 - 0
but if the header packet reaches the second switch, why can't it jump right into the third switch, so it goes like
4 - 0 - 0 - 0
3 - 1 - 0 - 0
2 - 1 - 1 - 0
1 - 1 - 1 - 1
Is it due to the latency reserving the link so the header had to wait for 1 time step or because the header has size of 2 packets in this example? It seems like Wormhole flow control is doing it.
This comment was marked helpful 0 times.
@raphaelk In terms of terminology, the whole thing is just one packet broken up, not four packets. In this example, the wait is because the header has a size of two pieces (don't know if they would be flits since it's a continuous flow of data as opposed to breaking up the packets into specific pieces).
This comment was marked helpful 0 times.
Under high contention, the output link is frequently blocked, so the packet coming in is stored in a packet buffer until it can be sent out. Thus if the link is continually blocked, cut-through reduces to store-and-forward.
This comment was marked helpful 0 times.