{rfName}
No

Indexed in

Citations

9

Altmetrics

Analysis of institutional authors

Hermenegildo, Manuel V.Corresponding Author

Share

June 9, 2019
Publications
>
Article
No

Non-strict independence-based program parallelization using sharing and freeness information

Publicated to: THEORETICAL COMPUTER SCIENCE. 410 (46): 4704-4723 - 2009-11-01 410(46), DOI: 10.1016/j.tcs.2009.07.044

Authors:

Gras, Daniel Cabeza; Hermenegildo, Manuel V
[+]

Affiliations

Univ Politecn Madrid, Fac Informat, E-28040 Madrid, Spain - Author

Abstract

The current ubiquity of multi-core processors has brought renewed interest in program parallelization. Logic programs allow studying the parallelization of programs with complex, dynamic data structures with (declarative) pointers in a comparatively simple semantic setting. In this context, automatic parallelizers which exploit and-parallelism rely on notions of independence in order to ensure certain efficiency properties. Non-strict independence is a more relaxed notion than the traditional notion of strict independence which still ensures the relevant efficiency properties and can allow considerable more parallelism. Non-strict independence cannot be determined solely at run-time (a priori) and thus global analysis is a requirement. However, extracting non-strict independence information from available analyses and domains is non-trivial. This paper provides on one hand an extended presentation of our classic techniques for compile-time detection of non-strict independence based on extracting information from (abstract interpretation-based) analyses using the now well understood and popular Sharing + Freeness domain. This includes algorithms for combined compile-time/run-time detection which involve special run-time checks for this type of parallelism. In addition, we propose herein novel annotation (parallelization) algorithms, URLP and CRLP, which are specially suited to non-strict independence. We also propose new ways of using the Sharing + Freeness information to optimize how the run-time environments of goals are kept apart during parallel execution. Finally. we also describe the implementation of these techniques in our parallelizing compiler and recall some early performance results. We provide as well an extended description of our pictorial representation of sharing and freeness information. (C) 2009 Elsevier B.V. All rights reserved.
[+]

Keywords

Abstract domainsAbstract interpretationAutomatic parallelizationDeclarative languagesLogic programmingLogic programsNon-strict independenceParallelismParallelizing compilersSharing and freeness

Quality index

Bibliometric impact. Analysis of the contribution and dissemination channel

The work has been published in the journal THEORETICAL COMPUTER SCIENCE due to its progression and the good impact it has achieved in recent years, according to the agency Scopus (SJR), it has become a reference in its field. In the year of publication of the work, 2009, it was in position , thus managing to position itself as a Q1 (Primer Cuartil), in the category Computer Science (Miscellaneous). Notably, the journal is positioned above the 90th percentile.

Independientemente del impacto esperado determinado por el canal de difusión, es importante destacar el impacto real observado de la propia aportación.

Según las diferentes agencias de indexación, el número de citas acumuladas por esta publicación hasta la fecha 2026-04-25:

  • WoS: 4
  • Scopus: 5
[+]

Impact and social visibility

From the perspective of influence or social adoption, and based on metrics associated with mentions and interactions provided by agencies specializing in calculating the so-called "Alternative or Social Metrics," we can highlight as of 2026-04-25:

  • The use of this contribution in bookmarks, code forks, additions to favorite lists for recurrent reading, as well as general views, indicates that someone is using the publication as a basis for their current work. This may be a notable indicator of future more formal and academic citations. This claim is supported by the result of the "Capture" indicator, which yields a total of: 4 (PlumX).

It is essential to present evidence supporting full alignment with institutional principles and guidelines on Open Science and the Conservation and Dissemination of Intellectual Heritage. A clear example of this is:

  • Assignment of a Handle/URN as an identifier within the deposit in the Institutional Repository: https://oa.upm.es/5368/

As a result of the publication of the work in the institutional repository, statistical usage data has been obtained that reflects its impact. In terms of dissemination, we can state that, as of

  • Views: 501
  • Downloads: 362
[+]

Leadership analysis of institutional authors

There is a significant leadership presence as some of the institution’s authors appear as the first or last signer, detailed as follows: First Author (Gras, Daniel Cabeza) and Last Author (HERMENEGILDO SALINAS, MANUEL DE).

the author responsible for correspondence tasks has been HERMENEGILDO SALINAS, MANUEL DE.

[+]

Awards linked to the item

The authors would like to thank M. Bruynooghe for suggesting improvements to the first version of the C I condition of Section 3.1 and E. Zaffanella and another (anonymous) reviewer of this journal version for numerous suggestions that have improved both the content and the presentation. The research presented in this paper (both the early contributions and the later extensions for this journal version) have been supported in part by the information Society Technologies program of the European Commission under projects PARFORCE, ACCLAIM, and MOBIUS, by the Spanish Ministry of Education under the IPL-D, MERIT, and DOVES projects, and by the Madrid Regional Government under the PROMESAS program. Manuel Hermenegildo was also supported in part by the Prince of Asturias Chair in Information Science and Technology at the U. of New Mexico. As mentioned before, this paper is an extended version of an earlier paper by the same authors which was published in the 1994 Static Analysis Symposium [6].
[+]