Big data processing with 1D-Crosspoint Arrays. Issue 3 (4th May 2023)

• Record Type: Journal Article
• Authors: An, Taeyoung; Yavuz Oruç, A.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 38:Issue 3(2023)
• Page Start: 249
• Page End: 274
• Publication Date: 2023-05-04
• Subjects: Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2023.2172574
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : Increased chip densities offer massive computation power to deal with fundamental big data operations such as searching and sorting. At the same time, the proliferation of processing elements (PEs) in such multicore chips together with the employment of more aggressive parallel algorithms cause the amount of space needed for interprocessor communications to dominate the overall chip space, potentially resulting in reduced computational efficiency. To overcome this issue, this paper 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 ) PEs as in linear array processor models. The switches between adjacent PEs are created using a cyclic permutation wiring idea with n ( n − 1 ) / 2 + 1 PEs and as many crosspoints. We demonstrate the versatility of this new parallel architecture by designing fast algorithms to sort and search a list of n elements with it. In particular, we show that finding a minimum, maximum, and searching a list of n elements can all be performed on this parallel architecture in O ( 1 ) time with additional O ( n ) elementary logic gates with O ( n ) fan-in and in O ( lg ⁡ n ) time with O ( 1 ) fan-in. We further show that sorting a list of n elements can also be carried out in O ( 1 ) time using O ( n ) additional elementary logic gates with O ( n ) fan-in and threshold logic gates on the same parallel architecture. The sorting time increases to O ( ( lg ⁡ n ) lg ⁡ lg ⁡ n ) if only elementary logic gates with O ( 1 ) fan-in are used. In addition, we establish how similar queries can be handled within the same order of time complexities. We use this new parallel architecture to perform sorting and searching on big data on three different models. The first of these models provides an efficient implementation of enumeration sorting and searching for moderate size big data sets. The second model offers increased parallelism by replication of the new parallel architecture but its hardware complexity limits its use to moderate size big data sets as well. The third model removes this limitation by introducing a tradeoff parameter between the time and hardware complexity of the overall computation, thereby providing an optimal use of available resources within a given chip-set space.