| Title | : | Parallelization Techniques for Processing Static and Dynamic Data |
| Speaker | : | Anju M A (IITM) |
| Details | : | Fri, 18 Aug, 2023 11:00 AM @ MR - I (SSB 233) |
| Abstract: | : | The advancements in computing hardware have introduced various types of parallel computers with great computing capabilities to the world. To exploit such computing powers for achieving high performance, it is ess ential to design efficient parallelization protocols and also to apply them at the right places in applications. Further, if the data processed by an application is dynamic in nature, it becomes challenging to parallelize the application, while maintaining its correct expected behaviour. We perform extensive research on both these aspects – (a) the design of efficient lock-based parallelization techniques, and (b) exploiting the opportunities for parallelization in applications. In both cases, our end goals are aligned – maximum performance gain of the underlying application that is parallelized. While developing our techniques, we have ensured that they work well for applications that process dynamic as well as static data. It has been established that the concurrent applications working with hierarchical data witness significant benefits due to multi-granularity locking (MGL) techniques compared to either fine or coarse-grained locking. We present MID (Multi-Interval DomLock), a new MGL technique to improve the degree of concurrency of interval-based hierarchical locking. MID is designed to work seamlessly with dynamic as well as static data. By augmenting each node with additional intervals, MID helps in reducing the unnecessary lock rejections due to false positive lock status of sub-hierarchies. Unleashing the hidden opportunities to exploit more concurrency allows the parallel threads to finish their operations quickly, leading to notable performance improvement. MID is general, and can be applied to any arbitrary hierarchy of trees, directed acyclic graphs (DAGs) and cycles. We illustrate the effectiveness of MID using STMBench7, a well known benchmark for parallel hierarchical application s, and with extensive experimental evaluation, show that it leads to significant throughput improvement (up to 141%, average 106%) over DomLock. We present a second locking technique named FlexiGran, which allows co-existence of hierarchical and fine-grained locks in an arbitrarily shaped hierarchy which can undergo structural alterations at run time, while allowing a user to control its memory usage by adding optional approximations. We illustrate the effectiveness of FlexiGran, which allows flexibility in the granularity of locking across lock requests, using STMBench7, and compare it empirically with two recent locking techniques, DomLock and HiFi. On a static hierarchy with more than a million nodes, FlexiGran achieves an average throughput improvement of around 159% and 374% on an average, compared to HiFi and DomLock respectively. In our third work, we present strategies to decide what parallelization techniques can be applied to which parts of an application, with clustering as the sample application. The huge size and dynamic nature of data processed by applications demand developing an approach that can handle the delta data with minimal updates to the underlying data structure, without complete re-clustering on every update. However, this poses synchronization challenges in parallelization. To address these challenges, we propose SLCoDD (Single-Linkage Clustering of Dynamic Data), a geometric distance based dynamic clustering and its multi-core parallelization using OpenMP. We demonstrate the effectiveness of SLCoDD using a suite of large synthetic and real-world inputs. SLCoDD’s fully dynamic version achieves a substantial geomean speedup of 5x over the dynamic sequential version. Compared to the static parallel version, SLCoDD achieves around 88% reduction in running time. |
