Technical Reports 2015

Technical report archive:

2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000


Yong Guo, Sungpack Hong, Hassan Chafi, Alexandru Iosup, and Dick Epema, Modeling, Analysis, and Experimental Comparison of Streaming Graph-Partitioning Policies: A Technical Report, PDS Technical Report PDS-2015-002

In recent years, many distributed graph-processing systems have been designed and developed to analyze large-scale graphs. For all distributed graph-processing systems, partitioning graphs is a key part of processing and an important aspect of achieve good processing performance. To keep low the performance of partitioning graphs, even when processing the ever-increasing modern graphs, many previous studies use lightweight streaming graph-partitioning policies. Although many such policies exist, currently there is no comprehensive study of their impact on load balancing and communication overheads, and on the overall performance of graph-processing systems. This relative lack of understanding hampers the development and tuning of new streaming policies, and could limit the entire research community to the existing classes of policies. We address these issues in this work. We begin by modeling the execution time of distributed graph-processing systems. By analyzing this model under the load of realistic graph-data characteristics, we propose a method to identify important performance issues and then design new streaming graph-partitioning policies to address them. By using three typical large-scale graphs and three popular graph-processing algorithms, we conduct comprehensive experiments to study the performance of our and of many alternative streaming policies on a real distributed graph-processing system. We also explore the impact on performance of using different real-world networks and of other real-world technical details. We further discuss the coverage of our model and method, and the design of future partitioning policies.



Jie Shen, Ana Lucia Varbanescu, Xavier Martorell, Henk Sips, A Study of Application Kernel Structure for Data
Parallel Applications
, PDS Technical Report PDS-2015-001

In this paper, we study the application kernel structure for data parallel applications. The application kernel structure includes two aspects, the number of kernels in the application and their execution flow. Based on the analysis of application kernel structure, we classify data parallel applications into five classes. To examine the coverage of the classification, we check five benchmark suites with a total of 86 applications, and show that the five classes cover all 86 applications. The classification makes it possible to design efficient partitioning strategies for data parallel applications, and to propose an application-driven method that selects the best performing partitioning strategy for a given workload.



Tribler logo
Bit-measure logo
Koala Grid Scheduler logo
Grench Mark logo
DAS 5 logo