Change search
ReferencesLink to record
Permanent link

Direct link
Evaluation and Optimization of Execution Plans for Fixpoint Iterative Algorithms in Large-Scale Graph Processing
KTH, School of Information and Communication Technology (ICT).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In large-scale graph processing, a fixpoint iterative algorithm is a set of operations where iterative computation is the core. The aim, in fact, is to perform repetitive operations refining a set of parameter values, until a fixed point is reached. To describe fixpoint iterative algorithms, template execution plans have been developed. In an iterative algorithm an execution plan is a set of dataflow operators describing the way in which parameters have to be processed in order to implement such algorithms. In the Bulk iterative execution plan all the parameters are recomputed for each iteration. Dependency plan calculates dependencies among vertices of a graph in order to iteratively update fewer parameters during each step. To do that it performs an extra pre-processing phase. This phase, however, is a demanding task especially in the first iterations where the amount of data is considerable. We describe two methods in order to address the preprocessing step of the Dependency plan. The first one exploits an optimizer which allows switching the plan during runtime, based on a cost model. We develop three cost models taking into account various features characterising the plan cost. The second method introduces optimizations that bypass the pre-processing phase. All the implementations are based on caching parameters values and so they are memory greedy. The experiments show that, while alternative implementation of Dependency plan does not give expected results in terms of per-iteration time, cost models are able to refine the existing basic cost model increasing accuracy. Furthermore, we demonstrate that switching plan during runtime is a successful strategy to decrease the whole execution time and improve performance.

Place, publisher, year, edition, pages
2016. , 57 p.
TRITA-ICT-EX, 2016:64
National Category
Information Systems, Social aspects
URN: urn:nbn:se:kth:diva-190102OAI: diva2:951367
Available from: 2016-09-12 Created: 2016-08-08 Last updated: 2016-09-12Bibliographically approved

Open Access in DiVA

fulltext(2573 kB)22 downloads
File information
File name FULLTEXT01.pdfFile size 2573 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Information Systems, Social aspects

Search outside of DiVA

GoogleGoogle Scholar
Total: 22 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link