National Technical Reports Library

The National Technical Information Service acquires, indexes, abstracts, and archives the largest collection of U.S. government-sponsored technical reports in existence. The NTRL offers online, free and open access to these authenticated government technical reports. Technical reports and documents in its repository may be available online for free either from the issuing federal agency, the U.S. Government Publishing Office’s Federal Digital System website, or through search engines.

Details

Transitive Closure on the Imagine Stream Processor.

DE2004828732

Publication Date	2004
Personal Author	Griem, G.
Page Count	12
Abstract	The increasing gap between processor and memory speeds is a well-known problem in modern computer architecture. The Imagine system is designed to address the processor-memory gap through streaming technology. Stream processors are best-suited for computationally intensive applications characterized by high data parallelism and producer-consumer locality with minimal data dependencies. This work examines an efficient streaming implementation of the computationally intensive Transitive Closure (TC) algorithm on the Imagine platform. We develop a tiled TC algorithm specifically for the Imagine environment, which efficiently reuses streams to minimize expensive off-chip data transfers. The implementation requires complex stream programming since the memory hierarchy and cluster organization of the underlying architecture are exposed to the Imagine programmer. Results demonstrate that limited performance of TC is achieved primarily due to the complicated data-dependencies of the blocked algorithm. This work is an ongoing effort to identify classes of scientific problems well-suited for streaming processors.
Keywords	Microprocessors Computer architecture Algorithms Performance Stream processors Imagine microprocessor
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Lawrence Berkeley National Lab., CA.; Department of Energy, Washington, DC.
Supplemental Notes	Sponsored by Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200513

Transitive Closure on the Imagine Stream Processor.

Transitive Closure on the Imagine Stream Processor.
DE2004828732

Publication Date	2004
Personal Author	Griem, G.
Page Count	12
Abstract	The increasing gap between processor and memory speeds is a well-known problem in modern computer architecture. The Imagine system is designed to address the processor-memory gap through streaming technology. Stream processors are best-suited for computationally intensive applications characterized by high data parallelism and producer-consumer locality with minimal data dependencies. This work examines an efficient streaming implementation of the computationally intensive Transitive Closure (TC) algorithm on the Imagine platform. We develop a tiled TC algorithm specifically for the Imagine environment, which efficiently reuses streams to minimize expensive off-chip data transfers. The implementation requires complex stream programming since the memory hierarchy and cluster organization of the underlying architecture are exposed to the Imagine programmer. Results demonstrate that limited performance of TC is achieved primarily due to the complicated data-dependencies of the blocked algorithm. This work is an ongoing effort to identify classes of scientific problems well-suited for streaming processors.
Keywords	Microprocessors Computer architecture Algorithms Performance Stream processors Imagine microprocessor
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Lawrence Berkeley National Lab., CA.; Department of Energy, Washington, DC.
Supplemental Notes	Sponsored by Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200513