View in EDS

Efficient Breadth-First Search on the Cell/BE Processor.

Saved in:
Bibliographic Details
Title: Efficient Breadth-First Search on the Cell/BE Processor.
Authors: Scarpazza, Daniele Paolo1 dpscarpazza@us.ibm.com, Villa, Oreste2,3 ovilla@elet.polimi.it, Petrini, Fabrizio1 fpetrin@us.ibm.com
Source: IEEE Transactions on Parallel & Distributed Systems. Oct2008, Vol. 19 Issue 10, p1381-1395. 28p. 3 Black and White Photographs, 5 Charts, 8 Graphs.
Subjects: Microprocessors, Parallel computer software, Computer software development, Broadband communication systems, Software architecture, Program transformation, Parallel programs (Computer programs), Computer system design & construction, Algorithms, Systems software, Integrated circuits, Computer software
Abstract: Multicore processors are an architectural paradigm shift that promises a dramatic increase in performance. But, they also bring an unprecedented level of complexity in algorithmic design and software development. In this paper, we describe the challenges involved in designing a Breadth-First Search (BFS) algorithm for the Cell Broadband Engine (Cell/BE) processor. The proposed methodology combines a high-level algorithmic design that captures the machine-independent aspects to guarantee portability with performance to future processors, with an implementation that embeds processor-specific optimizations. Using a fine-grained global coordination strategy derived from the Bulk-Synchronous Parallel (BSP) model, we have derived an accurate performance model that has guided the implementation and the optimization of our algorithm. Our experiments show an almost linear scaling over the number of used synergistic processing elements in the Cell/BE platform and compares favorably against other systems. On graphs that offer sufficient parallelism, the Cell/BE is typically an order of magnitude faster than conventional processors, such as the AMD Opteron, the Intel Pentium 4, and the Intel Woodcrest and custom-designed architectures such as the MTA-2 and BlueGene/L. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE 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 Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 34705820
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Efficient Breadth-First Search on the Cell/BE Processor.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Scarpazza%2C+Daniele+Paolo%22">Scarpazza, Daniele Paolo</searchLink><relatesTo>1</relatesTo><i> dpscarpazza@us.ibm.com</i><br /><searchLink fieldCode="AR" term="%22Villa%2C+Oreste%22">Villa, Oreste</searchLink><relatesTo>2,3</relatesTo><i> ovilla@elet.polimi.it</i><br /><searchLink fieldCode="AR" term="%22Petrini%2C+Fabrizio%22">Petrini, Fabrizio</searchLink><relatesTo>1</relatesTo><i> fpetrin@us.ibm.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Parallel+%26+Distributed+Systems%22">IEEE Transactions on Parallel & Distributed Systems</searchLink>. Oct2008, Vol. 19 Issue 10, p1381-1395. 28p. 3 Black and White Photographs, 5 Charts, 8 Graphs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Microprocessors%22">Microprocessors</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+computer+software%22">Parallel computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software+development%22">Computer software development</searchLink><br /><searchLink fieldCode="DE" term="%22Broadband+communication+systems%22">Broadband communication systems</searchLink><br /><searchLink fieldCode="DE" term="%22Software+architecture%22">Software architecture</searchLink><br /><searchLink fieldCode="DE" term="%22Program+transformation%22">Program transformation</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+programs+%28Computer+programs%29%22">Parallel programs (Computer programs)</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+system+design+%26+construction%22">Computer system design & construction</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Systems+software%22">Systems software</searchLink><br /><searchLink fieldCode="DE" term="%22Integrated+circuits%22">Integrated circuits</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Multicore processors are an architectural paradigm shift that promises a dramatic increase in performance. But, they also bring an unprecedented level of complexity in algorithmic design and software development. In this paper, we describe the challenges involved in designing a Breadth-First Search (BFS) algorithm for the Cell Broadband Engine (Cell/BE) processor. The proposed methodology combines a high-level algorithmic design that captures the machine-independent aspects to guarantee portability with performance to future processors, with an implementation that embeds processor-specific optimizations. Using a fine-grained global coordination strategy derived from the Bulk-Synchronous Parallel (BSP) model, we have derived an accurate performance model that has guided the implementation and the optimization of our algorithm. Our experiments show an almost linear scaling over the number of used synergistic processing elements in the Cell/BE platform and compares favorably against other systems. On graphs that offer sufficient parallelism, the Cell/BE is typically an order of magnitude faster than conventional processors, such as the AMD Opteron, the Intel Pentium 4, and the Intel Woodcrest and custom-designed architectures such as the MTA-2 and BlueGene/L. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE 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=34705820
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TPDS.2007.70811
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 28
        StartPage: 1381
    Subjects:
      – SubjectFull: Microprocessors
        Type: general
      – SubjectFull: Parallel computer software
        Type: general
      – SubjectFull: Computer software development
        Type: general
      – SubjectFull: Broadband communication systems
        Type: general
      – SubjectFull: Software architecture
        Type: general
      – SubjectFull: Program transformation
        Type: general
      – SubjectFull: Parallel programs (Computer programs)
        Type: general
      – SubjectFull: Computer system design & construction
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Systems software
        Type: general
      – SubjectFull: Integrated circuits
        Type: general
      – SubjectFull: Computer software
        Type: general
    Titles:
      – TitleFull: Efficient Breadth-First Search on the Cell/BE Processor.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Scarpazza, Daniele Paolo
      – PersonEntity:
          Name:
            NameFull: Villa, Oreste
      – PersonEntity:
          Name:
            NameFull: Petrini, Fabrizio
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2008
              Type: published
              Y: 2008
          Identifiers:
            – Type: issn-print
              Value: 10459219
          Numbering:
            – Type: volume
              Value: 19
            – Type: issue
              Value: 10
          Titles:
            – TitleFull: IEEE Transactions on Parallel & Distributed Systems
              Type: main
ResultId 1