The prevailing part of applications in modern high performance computing systems are data-intensive scientific computations. Thus, a considerable amount of energy is consumed by the I/O (Input/Output) subsystem performing I/O operations on terabytes of data. For better performance, each data file is split into stripes placed on distinct disks of a large array of disks. We have a complex systems consisting of many disks. The energy consumed by each disk depends on its rotational speed: the disk power consumption is quadratically proportional to the disk rotational speed. Thus, if we can perform some I/O operations at lower rate without degrading the performance of the overall computation, then we have opportunity for energy savings.

High performance computing applications are dominated by input-independent behaviour : The sequence of operations (also of I/O operations) does not depend on the values of input data. A compiler can effectively determine at compile time I/O system parameters:

• disk speeds
• data layouts
• disk data prefetching

Consider the following code fragment:

• for \( i=0 \) to \(N-1\) do
  • for \( j=0 \) to \( M-1 \) do
    • \( \ldots V_1[i][j] \ldots \)

• Let \(T_d\) denote the time (number of cycles) needed to read a single block \(D_i\) of data.
• Let \(T_c\) denote the time (number of cycles) needed to process a single block \(D_i\) of data.

Since I/O operations can be performed concurrently with CPU operations, the time efficiency of the algorithm can be increased by appropriate inserting data-prefetching instructions at compilation time. Our example code would be transformed by the compiler as follows:

• for \(i=0\) to \(N-1\) do
  • \(PF(\& V_1[i][0])\); /* prolog */
  • for \(jj=0\) to \(M-1-d\) step \(b_1\) do
    • /* steady-state */
    • \(PF(\& V_1[i][jj+d])\);
    • for \(j=jj\) to \(jj+b_1\) do
      • \(\ldots V_1[i][j] \ldots\)
  • for \(j=M-d\) to \(M-1\) do /* epilog */
    • \(\ldots V_1[i][j] \ldots\)

Here, the prefetch distance \(d\) (the time needed to cover the I/O latency, measured in iterations) can be calculated as follows: \[ d=\left\lceil\frac{T_d}{s+T_{pf}}\right\rceil, \] where

• \(T_d\) is estimated I/O latency to prefetch one block (measured in cycles),
• \(T_{pf}\) is the overhead of executing a prefetch instruction (measured in cycles),
• \(s \) is the number of cycles in the shortest path through the loop body.

Here, \(d\) iterations of \(j\) loop are required to hide I/O latency and \(b_1\) is the strip size used for stripe mining. Execution of this optimised code is illustrated by the following timing diagram:

So far, we have optimised the time efficiency. However, in our example, \(d\) is much lower than \(b_1\). By reducing the rotational speed of the disks we can save disk energy and increase prefetch distance without significant increase of the computation time:

Here, the lower height of the red blocks indicates the reduced power consumption of disks. We have reduced the rotational speed twice and, thus, the power consumption have been reduced four times.

1. What is the dependency between the rotational speed of disks and their power consumption?
2. Why could we reduce the speed of I/O devices without significant increase of overall computation time?
3. List some examples of algorithms with input-independent behaviour.