1 |
A Concurrent IFDS Dataflow Analysis Algorithm Using ActorsRodriguez, Jonathan David January 2010 (has links)
There has recently been a resurgence in interest in techniques for effective programming
of multi-core computers. Most programmers find general-purpose concurrent programming to be
extremely difficult. This difficulty severely limits the number of applications that
currently benefit from multi-core computers.
There already exist many concurrent solutions for the class of regular applications,
which include various algorithms for linear algebra.
For the class of irregular applications, which operate on dynamic and pointer- and graph-based
structures, efficient concurrent solutions have so far remained elusive.
Dataflow analysis applications, which are often found in compilers and
program analysis tools, have received particularly little attention
with regard to execution on multi-core machines.
Operating on the theory that the Actor model, which structures computations
as systems of asynchronously-communicating entities, is a more appropriate
method for representing irregular algorithms than the shared-memory model,
this work presents a concurrent Actor-based formulation of the IFDS,
or Interprocedural Finite Distributive Subset, dataflow analysis algorithm.
The implementation of this algorithm is done using the Scala language and its Actors
library. This algorithm achieves significant speedup on multi-core machines without using
any optimistic execution.
This work contributes to Actor research by showing how the Actor model can be practically
applied to a dataflow analysis problem.
This work contributes to static analysis research by showing how a dataflow analysis
algorithm can effectively make use of multi-core machines,
allowing the possibility of faster and more precise analyses.
|
2 |
A Concurrent IFDS Dataflow Analysis Algorithm Using ActorsRodriguez, Jonathan David January 2010 (has links)
There has recently been a resurgence in interest in techniques for effective programming
of multi-core computers. Most programmers find general-purpose concurrent programming to be
extremely difficult. This difficulty severely limits the number of applications that
currently benefit from multi-core computers.
There already exist many concurrent solutions for the class of regular applications,
which include various algorithms for linear algebra.
For the class of irregular applications, which operate on dynamic and pointer- and graph-based
structures, efficient concurrent solutions have so far remained elusive.
Dataflow analysis applications, which are often found in compilers and
program analysis tools, have received particularly little attention
with regard to execution on multi-core machines.
Operating on the theory that the Actor model, which structures computations
as systems of asynchronously-communicating entities, is a more appropriate
method for representing irregular algorithms than the shared-memory model,
this work presents a concurrent Actor-based formulation of the IFDS,
or Interprocedural Finite Distributive Subset, dataflow analysis algorithm.
The implementation of this algorithm is done using the Scala language and its Actors
library. This algorithm achieves significant speedup on multi-core machines without using
any optimistic execution.
This work contributes to Actor research by showing how the Actor model can be practically
applied to a dataflow analysis problem.
This work contributes to static analysis research by showing how a dataflow analysis
algorithm can effectively make use of multi-core machines,
allowing the possibility of faster and more precise analyses.
|
3 |
Fast and Scalable Static Analysis using Deterministic Concurrency / Snabb och skalbar statisk analys med hjälp av deterministisk samtida exekveringAckland, Patrik January 2017 (has links)
This thesis presents an algorithm for solving a subset of static analysis data flow problems known as Interprocedural Finite Distribute Subset problems. The algorithm, called IFDS-RA, is an implementation of the IFDS algorithm which is an algorithm for solving such problems. IFDS-RA is implemented using Reactive Async which is a deterministic, concurrent, programming model. The scalability of IFDS-RA is compared to the state-of-the-art Heros implementation of the IFDS algorithm and evaluated using three different taint analyses on one to eight processing cores. The results show that IFDS-RA performs better than Heros when using multiple cores. Additionally, the results show that Heros does not take advantage of multiple cores even if there are multiple cores available on the system. / Detta examensarbete presenterar en algoritm för att lösa en klass av problem i statisk analys känd som Interprocedural Finite Distribute Subset problem. Algoritmen, IFDS-RA, är en implementation av IFDS algoritmen som är utvecklad för att lösa denna typ av problem. IFDS-RA använder sig av Reactive Async som är en deterministisk programmeringsmodell för samtida exekvering av program. Prestendan evalueras genom att mäta exekveringstid för tre stycken taint analyser med en till åtta processorkärnor och jämförs med state-of-the-art implementationen Heros. Resultaten visar att IFDS-RA presterar bättre än Heros när de använder sig av flera processorkärnor samt att Heros inte använder sig av flera processorkärnor även om de finns tillgängliga.
|
Page generated in 0.0141 seconds