Analytic Utility Of Novel Threading Models In Distributed Graph Algorithms

Colloq: Speaker: 
Megan Cason
Colloq: Speaker Institution: 
Information Technology Laboratory, US Army Engineering R&D Center
Colloq: Date and Time: 
Mon, 2013-06-17 10:00
Colloq: Location: 
Building 5100, Room 262
Colloq: Host: 
Jeffrey S. Vetter
Colloq: Host Email:
Colloq: Abstract: 
Current analytic methods for judging distributed algorithms rely on communication abstractions that characterize performance assuming purely passive data movement and access. This assumption complicates the analysis of certain algorithms, such as graph analytics, which have behavior that is very dependent on data movement and modifying shared variables. This presentation will discuss an alternative model for analyzing theoretic scalability of distributed algorithms written with the possibility of active data movement and access. The mobile subjective model presented here confines all communication to 1) shared memory access and 2) executing thread state which can be relocated between processes, i.e., thread migration. Doing so enables a new type of scalability analysis, which calculates the number of thread relocations required, and whether that communication is balanced across all processes in the system. This analysis also includes a model for contended shared data accesses, which is used to identify serialization points in an algorithm. This presentation will show the analysis for a common distributed graph algorithm, and illustrate how this model could be applied to a real world distributed runtime software stack.
Colloq: Speaker Bio: 
Megan Cason is a Computer Scientist at the Information Technology Laboratory, US Army Engineering R&D Center.