ResII Computing

Нахождение ResMII
1. Сортируем инструкции по возрастанию степени свободы инструкции (степень свободы – количество функциональных блоков, на которых инструкция может выполняться).
2. Берем следующую инструкцию a из списка. Для каждого ресурса r: прибавляем сколько раз a использует r к UsageCount(r). Выбираем альтернативный блок с минимальным UsageCount.

The resource-constrained lower bound on the II, ResMII, is calculated by totaling, for each resource, the usage requirements imposed by one iteration of the loop. The exact ResMII can be computed by performing an optimal bin-packing of the reservation tables for all the operations, a computation that is of exponential complexity. Complex reservation tables and multiple alternatives make it worse yet and it is impractical, in general, to compute the ResMII exactly. Instead, an approximation to this exact lower bound is computed.
The ResMII is computed by first sorting the operations in the loop body in increasing order of the number of alternatives, i.e., degrees of freedom, and initializing the usage count of each resource to zero. At each step in the algorithm, the partial ResMII is defined to be the usage count of the most heavily used resource at that point. The operations are processed in sort order. For an operation with multiple alternatives, each alternative is selected in turn. The number of times it uses each resource is added to the current usage count for that resource in order to determine the partial ResMII that would result if this alternative were actually used. For each operation, that alternative is selected which yields the lowest partial ResMII. When all operations have been considered, the usage count for the most heavily used resource constitutes the ResMII. It is important to note that this selection between the alternatives is only for the purpose of computing the ResMII. During scheduling, the scheduler has complete freedom to select the alternative that will actually be used.
The method above yields an integer-valued ResMII. In general, the ResMII is a real-valued number and ought to be computed as such. For instance, if the floating-point adders are the most heavily used functional units, there are three of them and there are 8 add operations, the ResMII is 8/3. More generally, if the functional units can be partitioned into equivalence classes, such that all of

the functional units in a given equivalence class can perform exactly the same set of operations, and if the operations are such that each one can be performed by precisely one equivalence class, then the ResMII can be computed by taking ratio of the number of operations to be executed on a given equivalence class and dividing that number by the number of functional units in that equivalence class. The largest such ratio, across all of the equivalence classes, is the ResMII.
Unfortunately, many real machines do not possess any such structure, and there exists no good technique for computing the real-valued ResMII. One approximate way to do so is to conceptually unroll the loop U times, calculate the integer-valued ResMII for this unrolled loop, and then divide that by U.

page revision: 5, last edited: 15 Nov 2006 21:09