The grand challenges of computation today lie in the arena of effective parallel computation. Parallel execution of tasks, and parallel access to data, form the cornerstones of current efforts to address difficult computational problems, especially data intensive problems such as weather prediction, stress analysis of materials, the spread of pollutants, and navigation.
The promise of parallel computation, of being able to employ a large number of processors to accelerate computations dramatically, is enormous. However, the benefits of parallel computing have not been fully realized, in part because the ability to process information in parallel cannot be fully exploited unless the information needed can be retrieved from memory devices in parallel. Costs and current switching technology both impose limits on the number of memory devices available. Hence it happens that two processors capable of computation in parallel both issue a request to the same memory device (a ``memory conflict''), and one processor simply waits while the other proceeds.
Naturally, one wants to assign data to memory devices so as to minimize, or at least reduce, memory conflicts. Perhaps the most important special case of this problem is when the data forms a rectangular array of entries; then conflict--free access to rows, columns, diagonals, and sub--rectangles are each needed in various parallel algorithms. Finding the mapping from data elements to memory devices (a ``skewing scheme'') that affords conflict--free access to portions of the data is a difficult, and largely unsolved, problem.
A skewing scheme for a rectangular array that provides conflict--free access to rows and columns, and that uses the fewest possible memory modules, is equivalent to a latin rectangle. Euler studied these combinatorial structures in 1779; in the process, he launched a new research area that has evolved into the modern day discipline of combinatorial design theory. Basic research on latin rectangles and squares run to thousands of papers over the last two hundred years, and their study remains very active today.
Not surprisingly, much of this research is relevant to the conflict--free access problem for rectangular arrays. Conflict--free access to diagonals, for example, is afforded by diagonal latin squares. Most importantly, available constructions for latin squares afford a substantial battery of techniques for the construction of skewing schemes.
Two computer scientists (Kim and Kumar) and one discrete mathematician (Heinrich) first examined the large common ground between parallel memory access for rectangular arrays, and latin squares, in 1989. Since that time, combinatorial techniques have proved useful in determining both the existence and the impossibility of various desired skewing schemes.
Knowledge about skewing schemes has advanced because of the role of prior basic research in discrete mathematics. But a complete solution, even for rectangular arrays, is not at hand. Applied research on skewing schemes and their use in massive parallel computations is naturally needed. So also is basic research on latin squares. Determining the number of memory devices that are required to store rectangular array data in a conflict--free manner is a central question; basic research on the structure of latin squares is needed to address it.
Moreover, the basic research being undertaken on latin squares today has potential applications in a many different areas, and one literally never knows where the next significant application will arise.
Conflict--free access has connections to numerous other areas, such as combinatorial tiling, and number theory. A clear introduction to the area is given in H.A.G. Wijshoff, Data Organization in Parallel Computers, Kluwer Academic Publishers, 1989.
For an illustration of the use of techniques from discrete mathematics in the conflict--free access problem, see C.J. Colbourn and K.E. Heinrich, ``Conflict-free access to parallel memories'', J. Parallel Distributed Computing 14 (1992) 193--200.
Thu Sep 28 09:58:04 CDT 1995