Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
TRITA-ICT-EX, 2016:64
National Category
Information Systems
Identifiers
URN: urn:nbn:se:kth:diva-190102OAI: oai:DiVA.org:kth-190102DiVA: diva2:951367
Subject / course
Computer Science
Educational program
Degree of Master
Examiners
Available from: 2016-09-12 Created: 2016-08-08 Last updated: 2017-04-21Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 80 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

urn-nbn

Altmetric score

urn-nbn
Total: 98 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf