New Shape Analysis and Interprocedural Techniques for Automatic Parallelization of C Codes

Corbera, Francisco; Asenjo, Rafael; Zapata, Emilio
February 2002
International Journal of Parallel Programming;Feb2002, Vol. 30 Issue 1, p37
Academic Journal
Automatic parallelization of codes with complex data structures is becoming very important. These complex, and often recursive, data structures are widely used in scientific computing. Shape analysis is one of the key steps in the automatic parallelization of such codes. In this paper we extend the Static Shape Graph (SSG) method to enable the successful and accurate detection of complex doubly-linked structures. We have also included an interprocedural analysis in our framework. These techniques have been implemented in a compiler, which has been validated for several C codes. In particular, we present the results the compiler achieves for the C sparse LU factorization algorithm and for a recursive code generating a tree data structure. The output SSG perfectly describes the complex data structure used in these codes.


Related Articles

  • Object Serialization: A Study of Techniques of Implementing Binary Serialization in C++, Java and .NET. Tauro, Clarence J. M.; Ganesan, N.; Mishra, Saumya; Bhagwat, Anupama // International Journal of Computer Applications;May2012, Vol. 45, p25 

    The process of converting a data structure or object state into a storable format is referred to as serialization. The resurrection of the stored data in the same or another computer environment is referred to as deserialization. Binary Serialization is converting the object in binary format and...

  • Data Structure Should Not be the Weakest Link in IT-enablement. Schraml, Todd // Database Trends & Applications;Sep2005, Vol. 19 Issue 9, p26 

    This article focuses on the need to optimize data structures for information technology development process. Optimizing the development process impact the entire organization. More than simply writing good code and designing database structures that properly reflect the business rules, optimized...

  • Performance and Design are Independent. Schraml, Todd // Database Trends & Applications;Dec2005, Vol. 19 Issue 12, p26 

    The article focuses on the database design and database management (DBMS) performance. The normalized database design supporting an enterprise is devoid of physical performance considerations which flows form an exploration of an organization's requirements. In normalizing the organization's...

  • Satisfiability checking using Boolean Expression Diagrams. Williams, Poul F.; Andersen, Henrik R.; Hulgaard, Henrik // International Journal on Software Tools for Technology Transfer;Nov2003, Vol. 5 Issue 1, p4 

    In this paper we present an algorithm for determining satisfiability of general Boolean formulas which are not necessarily in conjunctive normal form. The algorithm extends the well-known Davis�Putnam algorithm to work on Boolean formulas represented using Boolean Expression Diagrams...

  • On the decidability of cryptographic protocols with open-ended data structures. Küsters, Ralf // International Journal of Information Security;2005, Vol. 4 Issue 1/2, p49 

    Formal analysis of cryptographic protocols has concentrated mainly on protocols with closed-ended data structures, i.e., protocols where the messages exchanged between principals have fixed and finite format. In many protocols, however, the data structures used are open-ended, i.e., messages...

  • Obsessed with music, Outlook list. Gibbs, Mark // Network World;10/24/2005, Vol. 22 Issue 42, p36 

    This article focuses on the move of the group called ID3, to work on a proposal to add table of contents and chapter data to any file that uses the ID3 tag. The ID3 tag is a data structure that is commonly used in a number of audio file formats, including MP3, AAC, WMA, and Ogg Vorbis, and...

  • Module.  // Network Dictionary;2007, p316 

    A definition of the term "Module" is presented. In computer software programming, module pertains to a software entity that groups a set of sub-programs/routines and data structures. Modules are units that can be compiled separately and can promote modularity and encapsulation, both of which can...

  • Digging Up the Dirt on Indexes. Delaney, Kalen // SQL Server Magazine;Dec2004, Vol. 6 Issue 12, p41 

    The article informs that in SQL Server, indexes are one of the most important data structures, they are the only means by which SQL Server can process huge tables in a reasonable amount of time. SQL Server offers very few documented tools for examining internal information (such as metadata)...

  • Are cookies really monsters? Carmichael, Matt // Advertising Age;11/18/1996, Vol. 67 Issue 47, p50 

    The article features the cookie, a technology developed by Netscape Communications Corp. A cookie is a bit of data that a Web site creator can send back and forth from the site to a person looking at it. Some sites with registration utilize cookies to permit user to store their user name and...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics