Indexing is a simple assignment function that matches the mathematical description of the data structure to the description of the processor network. In multiprocessors, hashing is used when the data domain does not have regular or symmetrical properties allowing it to be evenly distributed among the processors. Instead, a hashing function is used on each datum to generate the Id of the processor where that it will reside. If each processor is given the hashing function, then the knowledge of the location of each item of the domain in the processor network can be fully distributed. Hashing is straightforward in its implementation, but indexing can have some interesting subtleties, which we shall now explore.
Indexing Let's take a look at the problem of matrix multiplication .
Hence every element of C is the combination of a row of A and a column of B . Let's try to figure out a way to break down the C matrix among processors, so as to obtain an efficient decomposition, both in terms of its performance and in terms of the programming effort that will be needed on our part. In cases where the size of the matrix is larger than the number of processors, we will have to break C down into subsets to be distributed to each processor. B. Therefore, a mapping requiring each processor to compute individual rows of C , would require the matrix B to be stored in its entirety at each node of the processor network. If, on the other hand, we require a processor to compute the first column of C , then each terms in that column will depend on a different row of A , and on the first column of B .