Скачать с ютуб Exploring the Design Space for Message-Driven Systems for Dynamic Graph Processing using CCA в хорошем качестве

Exploring the Design Space for Message-Driven Systems for Dynamic Graph Processing using CCA

Fine granularity of operations, a large amount of latent parallelism, and irregular memory access are the properties of interest that have led to the work discussed in this dissertation. These properties are manifested in graph processing, with the edges representing a large amount of very fine-grain parallelism, having no general locality in terms of where they might point, rendering popular techniques not as useful. These popular techniques include: anticipating and staging of data guided by the principle of spatial locality, bulk synchronous models of task expression and synchronization that impose or assume a coarser granularity of operations, sending data to where the work needs to be performed, and static expression of parallelism rather than dynamic discovery at runtime from the graph data itself. Especially taken in the context of the end of Moore’s Law and Dennard scaling, a new architecture, along with its programming model and runtime, has become essential for immediate growth in processing performance. The thesis addresses this challenge and explores a new class of non-von Neumann architecture, along with a programming and data model, that replaces the conventional popular practices for future ultra-high scale computing. The thesis focuses on alternate approaches such as asynchronous message-driven computations that have the potential to expose the inherent latent parallelism of the graph structure at runtime by send work to where the vertex resides. Such a message-driven system comes with its own challenges of a programming model and language that is easy to write vertex-centric programs, along with new data structures and runtime support for dynamic task creation, load balancing and parallelization of the underlying graph data. The main contributions of this thesis are: 1) A programming and execution model that allows spawning tasks from within the vertex data at runtime. 2) An innovative vertex-centric data-structure, using the concept of Rhizomes, that parallelizes both the out-degree and in-degree load of vertex objects across many cores and yet provides a single programming abstraction to the vertex objects. 3) Language constructs for actions that send work to where the data resides, combining parallel expressiveness of Local Control Objects (LCOs) to implement asynchronous graph processing primitives. 4) Language and compiler aided runtime system support for task creation and execution that keep compute resources occupied with work when messages block on network due to congestion.