A Heuristic Approach for Single Path Pipeline Execution on Grid

In pipeline computation, a task is divided into a sequence of stages executed concurrently on different computing resources. When running on grid, the cost of pipeline computation depends not only on the computation time of each stage, but the communication time to send intermediate data from one st...

Full description

Saved in:
Bibliographic Details
Main Authors: Kijsipongse, E., Ngamsuriyaroj, S.
Format: Conference Proceeding
Language:English
Subjects:
Bandwidth
Computational efficiency
Computer science
Concurrent computing
Costs
Grid computing
Heuristic algorithms
heuristic mapping
Partitioning algorithms
pipeline placement
pipeline scheduling
Pipelines
Throughput
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In pipeline computation, a task is divided into a sequence of stages executed concurrently on different computing resources. When running on grid, the cost of pipeline computation depends not only on the computation time of each stage, but the communication time to send intermediate data from one stage to another as well. Thus, such stages must be placed on nodes with proper computing resources and the data transferred between successive stages must be on the highest bandwidth in order to achieve the maximum throughput. Obviously, finding the optimal placement of pipeline stages on grid nodes would not be easy. In this paper, we propose a heuristic algorithm called throughput pipeline to find the best pipeline placement on grid that gives the maximum throughput for the single path pipeline execution where the flow of jobs cannot be split due to data dependency constraint. Our approach considers simultaneously both pipeline partitioning and the data transfer path. The experiment running in a real grid environment gives higher throughput than other traditional placement algorithms.
ISSN:2160-4908
DOI:10.1109/GCC.2008.49