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

Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures

JOURNAL OF SUPERCOMPUTING 2011年第3期58卷 376-384页

作者： Sanjuan-Estrada, J. F. Casado, L. G. Garcia, I. Univ Almeria Dept Comp Architecture & Elect Almeria Spain Univ Malaga Dept Comp Architecture E-29071 Malaga Spain

This work studies how to adapt the number of threads of a parallel Interval Branch and Bound algorithm to the available computational resources based on its current performance. Basically, a thread can create a new thread that will process part of the ancestor workload. In this way, load balancing is inherent to the creation of threads. The applications in which we are interested use branch-and-bound algorithms which are highly irregular and therefore difficult to predict. The proposed methods can be used for more predictable algorithms as well. This research complements and does not substitute other devices that improve the exploitation of the system, such as dynamic scheduling policies or work-stealing. Several approaches are presented. They differ in the metrics used and in the need or not having to modify the Operating System (O.S.). The scenario for this research is just one multithreaded application running in a multicore architecture. Experimental results show that the appropriate number of running threads can be determined at run-time, avoiding having to statically establish the number of threads of an application. Thread creation decisions have to be made frequently to obtain better results, but are time-consuming. One of the presented models uses the existence of an idle processor to carry out these decisions, obtaining the desired results.

关键词： Multithreaded shared memory parallel processors Performance analysis Branch-and-bound Global optimization Irregularity

来源：评论

学校读者我要写书评

暂无评论

A DYNAMIC PROCESSOR ALLOCATION POLICY FOR MULTIPROGRAMMED shared-memory MULTIprocessors

引用

ACM TRANSACTIONS ON COMPUTER SYSTEMS 1993年第2期11卷 146-178页

作者： MCCANN, C VASWANI, R ZAHORJAN, J Univ. of Washington St. Louis MO Univ. of Washington St. Louis MO Univ. of Washington St. Louis MO

We propose and evaluate empirically the performance of a dynamic processor-scheduling policy for multiprogrammed shared-memory multiprocessors. The policy is dynamic in that it reallocates processors from one parallel job to another based on the currently realized parallelism of those jobs. The policy is suitable for implementation in production systems in that: It interacts well with very efficient user-level thread packages, leaving to them many low-level thread operations that do not require kernel intervention. It deals with thread blocking due to user I/O and page faults. It ensures fairness in delivering resources to jobs. Its performance, measured in terms of average job response time, is superior to that of previously proposed schedulers, including those implemented in existing systems. It provides good performance to very short, sequential (e.g., interactive) requests. We have evaluated our scheduler and compared it to alternatives using a set of prototype implementations running on a Sequent Symmetry multiprocessor. Using a number of parallel applications with distinct qualitative behaviors, we have both evaluated the policies according to the major criterion of overall performance and examined a number of more general policy issues, including the advantage of ''space sharing'' over ''time sharing'' the processors of a multiprocessor, and the importance of cooperation between the kernel and the application in reallocating processors between jobs. We have also compared the policies according to other criteria important in real implementations, in particular, fairness and response time to short, sequential requests. We conclude that a combination of performance and implementation considerations makes a compelling case for our dynamic scheduling policy.

关键词： shared memory parallel processors THREADS 2-LEVEL SCHEDULING

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：