检索结果-内蒙古大学图书馆

A performance-based parallel loop scheduling on grid environments

JOURNAL OF SUPERCOMPUTING 2007年第3期41卷 247-267页

作者： Shih, Wen-Chung Yang, Chao-Tung Tseng, Shian-Shyong Tunghai Univ Dept Comp Sci & Informat Engn High Performance Comp Lab Taichung 40704 Taiwan Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30010 Taiwan Asia Univ Dept Informat Sci & Applicat Taichung 41354 Taiwan

The effectiveness of loop self-scheduling schemes has been shown on traditional multiprocessors in the past and computing clusters in the recent years. However, parallel loop scheduling has not been widely applied to computing grids, which are characterized by heterogeneous resources and dynamic environments. In this paper, a performance-based approach, taking the two characteristics above into consideration, is proposed to schedule parallel loop iterations on grid environments. Furthermore, we use a parameter, SWR, to estimate the proportion of the workload which can be scheduled statically, thus alleviating the effect of irregular workloads. Experimental results on a grid testbed show that the proposed approach can reduce the completion time for applications with regular or irregular workloads. Consequently, we claim that parallel loop scheduling can benefit applications on grid environments.

关键词： parallel loop scheduling performance self-scheduling grid computing Globus Toolkit

来源：评论

学校读者我要写书评

暂无评论

Exploiting partial replication in unbalanced parallel loop scheduling on multicomputers

MICROPROCESSING AND MICROPROGRAMMING

引用

MICROPROCESSING AND MICROPROGRAMMING 1996年第8-9期41卷 645-658页

作者： Orlando, S Perego, R CNR CNUCEI-56126 PISAITALY

We consider the problem of scheduling parallel loops whose iterations operate on large array data structures and are characterized by highly varying execution times (unbalanced or non-uniform parallel loops), A general parallel loop implementation template for message-passing distributed-memory multiprocessors (multicomputers) is presented, Assuming that it is impossible to statically determine the distribution of the computational load on the data accessed, the template exploits a hybrid scheduling strategy, The data are partially replicated on the processor's local memories and iterations are statically scheduled until first load imbalances are detected. At this point an effective dynamic scheduling technique is adopted to move iterations among nodes holding the same data. Most of the communications needed to implement dynamic load balancing are overlapped with computations, as a very effective prefetching policy is adopted. The template scales very well, since knowing where data are replicated makes it possible to balance the load without introducing high overheads. In the paper a formal characterization of load imbalance related to a generic problem instance is also proposed. This characterization is used to derive an analytical cost model for the template, and in particular, to tune those parameters of the template that depend on the costs related to the specific features of the target machine and the specific problem. The template and the related cost model are validated by experiments conducted on a 128-node nCUBE 2, whose results are reported and discussed.

关键词： parallel loop scheduling load balancing implementation template

来源：评论

学校读者我要写书评

暂无评论

An intelligent parallel loop scheduling for parallelizing compilers

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2000年第2期16卷 169-200页

作者： Fann, YW Yang, CT Tseng, SS Tsai, CJ Natl Chiao Tung Univ Dept Comp & Informat Sci Hsinchu 300 Taiwan Natl Space Program Off ROCSAT Ground Syst Sect Hsinchu 300 Taiwan

In this paper we propose a knowledge-based approach to solving loop-scheduling problems. A rule-based system, called IPLS, is developed by combining a repertory grid and an attribute ordering table to construct a knowledge base. IPLS chooses an appropriate scheduling algorithm by inferring some features of loops and assigning parallel loops to multiprocessors to achieve significant speedup. Because more attributes are proposed, the accuracy of selection of an appropriate scheduling method is improved. In addition, the refined IPLS system can automatically adjust the attributes in the knowledge base according to profile information;therefore, IPLS has the capability of feedback learning. The experimental results show that our approach can achieve greater speedup on multiprocessor systems than can others.

关键词： parallelizing compiler parallel loop scheduling knowledge-based system multiprocessor systems speedup

来源：评论

学校读者我要写书评

暂无评论

Towards Robust Data-driven parallel loop scheduling Using Bayesian Optimization 27

Towards Robust Data-driven Parallel Loop Scheduling Using Ba...

引用

IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)

作者： Kim, Khu-rai Kim, Youngjae Park, Sungyong Sogang Univ Elect Engn Dept Seoul South Korea Sogang Univ Comp Sci & Engn Dept Seoul South Korea

ISBN: (纸本)9781728149516;9781728149509

Efficient parallelization of loops is critical to improving the performance of high-performance computing applications. Many classical parallel loop scheduling algorithms have been developed to increase parallelization efficiency. Recently, workload-aware methods were developed to exploit the structure of workloads. However, both classical and workload-aware scheduling methods lack what we call robustness. That is, most of these scheduling algorithms tend to be unpredictable in terms of performance or have specific workload patterns they favor. This causes application developers to spend additional efforts in finding the best suited algorithm or tune scheduling parameters. This paper proposes Bayesian Optimization augmented Factoring Self-scheduling (BO FSS), a robust data-driven parallel loop scheduling algorithm. BO FSS is powered by Bayesian Optimization (BO), a machine learning based optimization algorithm. We augment a classical scheduling algorithm, Factoring Self-scheduling (FSS), into a robust adaptive method that will automatically adapt to a wide range of workloads. To compare the performance and robustness of our method, we have implemented BO FSS and other loop scheduling methods on the OpenMP framework. A regret-based metric called performance regret is also used to quantify robustness. Extensive benchmarking results show that BO FSS performs fairly well in most workload patterns and is also very robust relative to other scheduling methods. BO FSS achieves an average of 4% performance regret. This means that even when BO FSS is not the best performing algorithm on a specific workload, it stays within a 4 percentage points margin of the best performing algorithm.

关键词： parallel loop scheduling Bayesian Optimization parallel Computing OpenMP

来源：评论

学校读者我要写书评

暂无评论

Using hybrid MPI and OpenMP programming to optimize communications in parallel loop self-scheduling schemes for multicore PC clusters

引用

JOURNAL OF SUPERCOMPUTING 2012年第1期60卷 31-61页

作者： Wu, Chao-Chin Lai, Lien-Fu Yang, Chao-Tung Chiu, Po-Hsun Natl Changhua Univ Educ Dept Comp Sci & Informat Engn Changhua 500 Taiwan Tunghai Univ Dept Comp Sci & Informat Engn High Performance Comp Lab Taichung 40704 Taiwan

Recently, a series of parallel loop self-scheduling schemes have been proposed, especially for heterogeneous cluster systems. However, they employed the MPI programming model to construct the applications without considering whether the computing node is multicore architecture or not. As a result, every processor core has to communicate directly with the master node for requesting new tasks no matter the fact that the processor cores on the same node can communicate with each other through the underlying shared memory. To address the problem of higher communication overhead, in this paper we propose to adopt hybrid MPI and OpenMP programming model to design two-level parallel loop self-scheduling schemes. In the first level, each computing node runs an MPI process for inter-node communications. In the second level, each processor core runs an OpenMP thread to execute the iterations assigned for its resident node. Experimental results show that our method outperforms the previous works.

关键词： parallel loop scheduling Cluster computing Multicore architecture MPI programming OpenMP programming Hybrid programming

来源：评论

学校读者我要写书评

暂无评论

Performance-Based parallel loop Self-scheduling on Heterogeneous Multicore PC Clusters

Performance-Based Parallel Loop Self-scheduling on Heterogen...

引用

2nd International Conference on High Performance Computing and Applications

作者： Yang, Chao-Tung Chang, Jen-Hsiang Wu, Chao-Chin Tunghai Univ High Performance Comp Lab Dept Comp Sci Taichung 40704 Taiwan Natl Changhua Univ Educ Dept Comp Sci & Informat Engn Changhua 50074 Taiwan

ISBN: (纸本)9783642118418

In recent years. Multicore computers have been widely included in cluster systems. They adopt shared memory architectures. However, previous researches on parallel loop self-scheduling did not consider the feature of multicore computers. It is more suitable for shared-memory multiprocessors to adopt OpenMP for parallel programming. In this paper, we propose a performance-based approach that partitions loop iterations according to the performance weighting of cluster nodes. Because the iterations assigned to one MPI process will be processed in parallel by OpenMP threads running by the processor cores in the same computational node, the number of loop iterations to be allocated to one computational node at each scheduling step also depends on the number of processor cores in that node. Experimental results show that the proposed approach performs better than previous schemes.

关键词： Self-scheduling parallel loop scheduling Multicore Cluster OpenMP MPI

来源：评论

学校读者我要写书评

暂无评论

SUPPLE: An efficient run-time support for non-uniform parallel loops

引用

JOURNAL OF SYSTEMS ARCHITECTURE 1999年第15期45卷 1323-1343页

作者： Orlando, S Perego, R CNR CNUCE I-56126 Pisa Italy Univ Ca Foscari Venezia Dipartimento Matemat Applicata & Informat I-30173 Venezia Mestre Italy

This paper presents SUPPLE (SUPort for parallel loop Execution), an innovative run-time support for the execution of parallel loops with regular stencil data references and non-uniform iteration costs. SUPPLE relies upon a static block data distribution to exploit locality, and combines static and dynamic policies for scheduling non-uniform iterations. It adopts, as far as possible, a static scheduling policy derived from the owner computes rule, and moves data and iterations among processors only if a load imbalance actually occurs. SUPPLE always tries to overlap communications with useful computations by reordering loop iterations and prefetching remote ones in the case of workload imbalance. The SUPPLE approach has been validated by many experimental results obtained by running a multidimensional flame simulation kernel on a 64-node Gray T3D. We have fed the benchmark code with several synthetic input data sets built on the basis of a load imbalance model. We have compared our results with those obtained with a CRAFT Fortran implementation of the benchmark. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： data parallelism parallel loop scheduling load balancing run-time supports compiler optimizations

来源：评论

学校读者我要写书评

暂无评论

Using knowledge-based techniques on loop parallelization for parallelizing compilers

引用

parallel COMPUTING 1997年第3期23卷 291-309页

作者： Yang, CT Tseng, SS Chuang, CD Shih, WC NATL CHIAO TUNG UNIV DEPT COMP & INFORMAT SCIHSINCHU 300TAIWAN

In this paper we propose a knowledge-based approach for solving data dependence testing and loop scheduling problems. A rule-based system, called the K-Test, is developed by repertory grid and attribute ording table to construct the knowledge base. The K-Test chooses an appropriate testing algorithm according to some features of the input program by using knowledge-based techniques, and then applies the resulting test to detect data dependences for loop parallelization. Another rule-based system, called the KPLS, is also proposed to be able to choose an appropriate scheduling by inferring some features of loops and assign parallel loops on multiprocessors for achieving high speedup. The experimental results show that the graceful speedup obtained by our compiler is obvious.

关键词： parallelizing compiler data dependence testing loop parallelization parallel loop scheduling knowledge-based repertory grid analysis speedup

来源：评论

学校读者我要写书评

暂无评论

An effective processor allocation strategy for multiprogrammed shared-memory multiprocessors

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 1997年第12期8卷 1246-1258页

作者： Yue, KK Lilja, DJ Sun Microsyst Inc Palo Alto CA 94303 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

Existing techniques for sharing the processing resources in multiprogrammed shared-memory multiprocessors, such as time-sharing, space-sharing, and gang-scheduling, typically sacrifice the performance of individual parallel applications to improve overall system utilization. We present a new processor allocation technique called loop-Level Process Control (LLPC) that dynamically adjusts the number of processors an application is allowed to use for the execution of each parallel section of code, based on the current system load. This approach exploits the maximum parallelism possible for each application without overloading the system. We implement our scheme on a Silicon Graphics Challenge multiprocessor system and evaluate its performance using applications from the Perfect Club benchmark suite and synthetic benchmarks. Our approach shows significant improvements over traditional time-sharing and gang-scheduling. It has performance comparable to, or slightly better than, static space-sharing, but our strategy is more robust since, unlike static space-sharing, it does not require a priori knowledge of the applications' parallelism characteristics.

关键词： parallel loop scheduling processor allocation operating system multiprogramming shared-memory multiprocessors

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Machine Learning Approach to scheduling parallel loops With Bayesian Optimization

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2021年第7期32卷 1815-1827页

作者： Kim, Khu-rai Kim, Youngjae Park, Sungyong Sogang Univ Dept Elect Engn Seoul 04107 South Korea Sogang Univ Dept Comp Sci & Engn Seoul 04107 South Korea

This article proposes Bayesian optimization augmented factoring self-scheduling (BO FSS), a new parallel loop scheduling strategy. BO FSS is an automatic tuning variant of the factoring self-scheduling (FSS) algorithm and is based on Bayesian optimization (BO), a black-box optimization algorithm. Its core idea is to automatically tune the internal parameter of FSS by solving an optimization problem using BO. The tuning procedure only requires online execution time measurement of the target loop. In order to apply BO, we model the execution time using two Gaussian process (GP) probabilistic machine learning models. Notably, we propose a locality-aware GP model, which assumes that the temporal locality effect resembles an exponentially decreasing function. By accurately modeling the temporal locality effect, our locality-aware GP model accelerates the convergence of BO. We implemented BO FSS on the GCC implementation of the OpenMP standard and evaluated its performance against other scheduling algorithms. Also, to quantify our method's performance variation on different workloads, or workload-robustness in our terms, we measure the minimax regret. According to the minimax regret, BO FSS shows more consistent performance than other algorithms. Within the considered workloads, BO FSS improves the execution time of FSS by as much as 22% and 5% on average.

关键词： Frequency selective surfaces Task analysis Heuristic algorithms Dynamic scheduling Optimization scheduling algorithms Copper parallel loop scheduling Bayesian optimization parallel computing OpenMP

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：