A Heuristic Approach for Single Path Pipeline Execution on Grid

• 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
• ISSN: 2160-4908
• DOI: 10.1109/GCC.2008.49

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.