next up previous

Exercise 10: An analysis of memory cycle time.

Figure 21: Gantt chart for 8-way interleaved memory.

A Gantt chart can be used to show how interleaved memory works by drawing one row for each memory bank. Mark the time line in units of processor cycles. If a processor requests an item from bank b at time t, draw a line in row b starting at time t and continuing for n units, where n is the memory cycle time. Figure 21 shows the Gantt chart for an 8-way interleaved memory in a system where the processor cycle time is 10ns and the memory cycle time is 40ns. The chart illustrates which memories are busy when the processor requests items from successive memory cells. Asterisks on the time line indicate when data items reach the processor (assuming data is delivered on the last memory cycle). Asterisks in every column indicate the memory is performing at its full potential, i.e. there are no bank conflicts.

Use a Gantt chart to show that for a system with 16 memory banks, 12.5ns processor cycle time, and 50ns memory cycle time, there will be no conflicts when the stride is 2 or 4, but there will be conflicts when the stride is 8 or 16. (NOTE: these cycle times and interleaving factors are taken from the Cray-1).