There has recently been a resurgence in interest in techniques for effective programmingof multi-core computers. Most programmers find general-purpose concurrent programming to beextremely difficult. This difficulty severely limits the number of applications thatcurrently 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-basedstructures, efficient concurrent solutions have so far remained elusive.Dataflow analysis applications, which are often found in compilers andprogram analysis tools, have received particularly little attentionwith regard to execution on multi-core machines.Operating on the theory that the Actor model, which structures computationsas systems of asynchronously-communicating entities, is a more appropriatemethod 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 Actorslibrary. This algorithm achieves significant speedup on multi-core machines without usingany optimistic execution.This work contributes to Actor research by showing how the Actor model can be practicallyapplied to a dataflow analysis problem.This work contributes to static analysis research by showing how a dataflow analysisalgorithm can effectively make use of multi-core machines,allowing the possibility of faster and more precise analyses.
【 预 览 】
附件列表
Files
Size
Format
View
A Concurrent IFDS Dataflow Analysis Algorithm Using Actors