Friday, January 11, 2013

The analysis of algorithms and MMIXAL.NET

Let's discuss how MMIXAL.NET can help to analyze algorithms. In particular, we'll consider the sorting by counting algorithm. This method is based on the idea that the jth key in the final sorted sequence is greater than exactly j - 1 of the other keys.
We need to compare K(j) key with K(i) key for 1 < j < i, 1 < i < N. MMIXAL code that implements the algorithm is given below (to enlarge the picture click on it).

InputBuf contains the keys to sort. This algorithm involves no movement of records. CountBuf[j] tells us where to move InputBuf[j] record. For our program, CountBuf will contain the following data: 6,1,8,0,15,3,14,4,10,5,2,7,9,11,13,12
It means InputBuf[4] is the smallest key and InputBuf[5] contains the biggest key.

At the end of the program's execution MMIXAL.NET prints
_ the total number of instructions executed;
_ the number of units that represents the clock cycle time or oops in a pipelined implementation;
_ the number of memory references or mems that the program uses;
_ the profile of the program.
See picture below.

Program's profile contains a frequency (fr) of instruction's execution. The running time of this program is 7N+7A+3B+1 units,where
_ N is the number of records to sort;
_ A is the number of choices of two things from a set of N objects (N! / 2!(N-2)!);
_B is the number of pairs of indices for which j < i and Kj > Ki.
Thus, B is the number of inversions of the permutation K1 K2 ... KN. The min value of B is 0 and max value is (N**2-N)/2.

So our program requires between 3.5N**2 + 3.5N + 1 and 5N**2 + 2N + 1 units of a time. The factor N**2 dominates this running time. It shows that the sorting by counting algorithm is not an efficient way to sort when N is large. Doubling the number of records increases the running time fourfold.