Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Parallel cost analysis
Albert E., Correas J., Johnsen E., Pun K., Román-Díez G. ACM Transactions on Computational Logic19 (4):1-37,2018.Type:Article
Date Reviewed: Apr 2 2021

In this paper, the authors present “static cost analysis for distributed systems that exploits the parallelism among distributed locations to infer a more precise estimation of the parallel cost.” Such a parallel cost analysis can be of use when applications can exploit the parallelism available at distributed locations.

Here, the authors present a modification of a cooperative concurrency model, a model that is being increasingly adopted for distributed and multi-core systems as it allows for some restrictions, for example, limiting interleaving analysis to synchronization points explicit in the program. This contrasts with the more widely used multi-threaded concurrency models that consider “an exponential explosion in the number of traces [to study].” To enable cooperative concurrency analysis, the authors compute “with different levels of precision: (a) the naive approach, using the set of nodes contained in the path expressions; (b) unfolding all disjunctions of the path expression; and (c) filtering infeasible paths.”

The paper include a small practical example: “a program--consisting of ~1,400 lines of code--which models a supermarket cash desk line.” Future work will incorporate analysis information about scheduling policies, which could be different at different locations.

Experimental results indicate that the parallel cost analysis presented in this paper is feasible and accurate, and could potentially provide “significant [cost] improvements with respect to the serial cost analysis,” reaching up to ~50 percent when combined with the filtering of infeasible paths. In another scenario, they “show that the naive approach and the unfolding disjunctions approach [perform at] 75 percent and 73.4 percent of the sequential upper bound, respectively,” while the filtering paths approach takes much longer. Thus, the application of this method requires “tradeoff[s] between the precision that can be achieved and the computational time to obtain the upper bound.”

To summarize, distributed and multi-core computing are becoming foundational to modern-day computing, with software systems expected to proactively support massively parallel execution. While traditional analysis of parallelism has focused on exploiting parallelism among independent tasks, in this work the authors explore “a model of computation that separates the asynchronous spawning of new tasks to different locations for task processing from the synchronization between these tasks.” While this concept is intuitive, it is nice to see it applied in a systematic way.

Reviewer:  Srini Ramaswamy Review #: CR147231 (2108-0212)
Bookmark and Share
  Featured Reviewer  
 
General (D.2.0 )
 
 
Distributed Programming (D.1.3 ... )
 
 
Formal Methods (D.2.4 ... )
 
 
Programming Languages (D.3 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Development of distributed software
Shatz S. (ed), Macmillan Publishing Co., Inc., Indianapolis, IN, 1993. Type: Book (9780024096111)
Aug 1 1994
Fundamentals of software engineering
Ghezzi C., Jazayeri M., Mandrioli D., Prentice-Hall, Inc., Upper Saddle River, NJ, 1991. Type: Book (013820432)
Jul 1 1992
Software engineering
Sodhi J., TAB Books, Blue Ridge Summit, PA, 1991. Type: Book (9780830633425)
Feb 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy