A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs.
Saved in:
| Title: | A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs. |
|---|---|
| Authors: | Areias, Miguel1 miguel-areias@dcc.fc.up.pt, Rocha, Ricardo1 ricroc@dcc.fc.up.pt |
| Source: | International Journal of Parallel Programming. Jun2016, Vol. 44 Issue 3, p386-406. 21p. |
| Subjects: | Prolog (Computer program language), Computer systems, Synchronization, Cache memory, Computer architecture |
| Abstract: | Tabling is an implementation technique that improves the declarativeness and expressiveness of Prolog systems in dealing with recursion and redundant sub-computations. A critical component in the design of a concurrent tabling system is the implementation of the table space. One of the most successful proposals for representing tables is based on a two-level trie data structure, where one trie level stores the tabled subgoal calls and the other stores the computed answers. In previous work, we have presented a sophisticated lock-free design where both levels of the tries where shared among threads in a concurrent environment. To implement lock-freedom we used the CAS atomic instruction that nowadays is widely found on many common architectures. CAS reduces the granularity of the synchronization when threads access concurrent areas, but still suffers from problems such as false sharing or cache memory effects. In this work, we present a simpler and efficient lock-free design based on hash tries that minimizes these problems by dispersing the concurrent areas as much as possible. Experimental results in the Yap Prolog system show that our new lock-free design can effectively reduce the execution time and scales better than previous designs. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Parallel Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 114786150 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Areias%2C+Miguel%22">Areias, Miguel</searchLink><relatesTo>1</relatesTo><i> miguel-areias@dcc.fc.up.pt</i><br /><searchLink fieldCode="AR" term="%22Rocha%2C+Ricardo%22">Rocha, Ricardo</searchLink><relatesTo>1</relatesTo><i> ricroc@dcc.fc.up.pt</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Parallel+Programming%22">International Journal of Parallel Programming</searchLink>. Jun2016, Vol. 44 Issue 3, p386-406. 21p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Prolog+%28Computer+program+language%29%22">Prolog (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Synchronization%22">Synchronization</searchLink><br /><searchLink fieldCode="DE" term="%22Cache+memory%22">Cache memory</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+architecture%22">Computer architecture</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Tabling is an implementation technique that improves the declarativeness and expressiveness of Prolog systems in dealing with recursion and redundant sub-computations. A critical component in the design of a concurrent tabling system is the implementation of the table space. One of the most successful proposals for representing tables is based on a two-level trie data structure, where one trie level stores the tabled subgoal calls and the other stores the computed answers. In previous work, we have presented a sophisticated lock-free design where both levels of the tries where shared among threads in a concurrent environment. To implement lock-freedom we used the CAS atomic instruction that nowadays is widely found on many common architectures. CAS reduces the granularity of the synchronization when threads access concurrent areas, but still suffers from problems such as false sharing or cache memory effects. In this work, we present a simpler and efficient lock-free design based on hash tries that minimizes these problems by dispersing the concurrent areas as much as possible. Experimental results in the Yap Prolog system show that our new lock-free design can effectively reduce the execution time and scales better than previous designs. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Journal of Parallel Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=114786150 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10766-014-0346-1 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 21 StartPage: 386 Subjects: – SubjectFull: Prolog (Computer program language) Type: general – SubjectFull: Computer systems Type: general – SubjectFull: Synchronization Type: general – SubjectFull: Cache memory Type: general – SubjectFull: Computer architecture Type: general Titles: – TitleFull: A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Areias, Miguel – PersonEntity: Name: NameFull: Rocha, Ricardo IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun2016 Type: published Y: 2016 Identifiers: – Type: issn-print Value: 08857458 Numbering: – Type: volume Value: 44 – Type: issue Value: 3 Titles: – TitleFull: International Journal of Parallel Programming Type: main |
| ResultId | 1 |
