1D-CROSSPOINT ARRAY AND ITS CONSTRUCTION, APPLICATION TO BIG DATA PROBLEMS, AND HIGHER DIMENSION VARIANTS

Abstract

Increased chip densities offer massive computation power to deal with fundamental bigdata operations such as sorting. At the same time the proliferation of processing elements (PEs) in settings such as High Performance Computers(HPCs) or servers together with the employment of more aggressive parallel algorithms cause the interprocessor communications to dominate the overall computation time, potentially resulting in reduced computational efficiency. To overcome this issue, this dissertation introduces a new architecture that uses simple crosspoint switches to pair PEs instead of a complex interconnection network. This new architecture may be viewed as a “quadratic” array of processors as it uses O(n^2) PEs rather than O(n) as in linear array processor models. In addition, three different models for sorting big data in a distributed com- puting environment such as Cloud computing are presented. With the most realistic model of the three, we demonstrate that the high parallelism made possible by the simple communication channels overcomes the seemingly excessive hardware complexity and performs comparable to or better than existing algorithms. Furthermore, two additional algorithms of matrix multiplica- tion and triangle counting for the 1D-Crosspoint Array are introduced and analyzed. Lastly, two higher dimensional variants, 2D- and 3D-Crosspoint Array are also proposed with a construction method, which succeeds in reducing the number of PEs required by utilizing the communication channels in the added dimensions.