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

Brazilian Symposium on Computing System Engineering (SBESC)

作者： Igor K. Pinotti Thais Webber Natanael Ribeiro Carlos N. Fraga Rubem D. R. Fagundes César Marcon PPGCC-Programa de Pós-Graduação em Ciência da Computação Pontifícia Universidade Católica do Rio Grande do Sul Porto Alegre Brazil PPGCC-Programa de Pós-Graduação em Ciência da Computação PPGEE-Programa de Pós-Graduação em Engenharia Elétrica Pontifícia Universidade Católica do Rio Grande do Sul Porto Alegre Brazil

Several new applications have high complexity degree, requiring high processing rate and memory usage. Multiprocessor System-on-Chip (MPSoC) is a promising architecture to fulfill these requirements, due to its high parallelism that enables several tasks been executed at the same time. One problem in current heterogeneous MPSoC design is application's tasks partitioning aiming energy consumption minimization and load balance. In order to optimize partition problems, many algorithms have been applied to generate quality solutions. This work aims to analyze and compare stochastic and heuristic partitioning algorithms for obtaining low energy consumption and load balance when applied to tasks partitioning onto heterogeneous MPSoC.

关键词： Program processors partitioning algorithms Energy consumption Tiles Computer architecture Algorithm design and analysis Cost function

来源：评论

学校读者我要写书评

暂无评论

Evaluation of automatic domain partitioning algorithms for parallel finite element analysis

引用

INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING 1997年第6期40卷 1025-1051页

作者： Hsieh, SH Paulino, GH Abel, JF CORNELL UNIV SCH CIVIL & ENVIRONM ENGN ITHACA NY 14853 USA

This paper studies and compares the domain partitioning algorithms presented by Farhat,(1) Al-Nasra and Nguyen,(2) Malone,(3) and Simon(4)/Hsieh et al.(5,6) for load balancing in parallel finite element analysis. Both the strengths and weaknesses of these algorithms are discussed. Some possible improvements to the partitioning algorithms are also suggested and studied. A new approach for evaluating domain partitioning algorithms is described. Direct numerical comparisons among the considered partitioning algorithms are then conducted using this suggested approach with both regular and irregular finite element meshes of different order and dimensionality. The test problems used in the comparative studies along with the results obtained provide a set of benchmark examples for other researchers to evaluate both new and existing partitioning algorithms. In addition, interactive graphics tools used in this work to facilitate the evaluation and comparative studies are presented.

关键词： algorithms domain partitioning load balancing mesh partitioning parallel finite element analysis partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT PARALLEL RANGE SEARCHING AND partitioning algorithms*

引用

Parallel algorithms and Applications 2001年第4期16卷 301-317页

作者： Amitava Datta - e-mail: datta@cs.uwa.edu.au.[a] [a] Department of Computer Science & Software Engineering The University of Western Australia Perth WA Australia

We present an optimal parallel construction of the range tree data structure and use this construction to solve several geometric partitioning problems. In the range tree, we show how to perform a count-mode orthogonal range query in 0(log n) time by a single processor and a report mode orthogonal range query in 0(log n) time using 0(1 + log n) processors, where k is the number of points inside the query range. We consider partitioning problems of the following nature. Given a planar point set S (∣S∣ = ri) a measure μacting on 5 and a pair of values μ1 and μ2,the task is to find a partition of S into two components S1and S2(S = S1U S2) such that μ(S1) =μ1 for i=1, 2. We consider several measures like diameter under L∞ and l1metric; area, perimeter of the smallest enclosing axes-parallel rectangle; and the side length of the smallest enclosing axes-parallel square. All our parallel algorithms foi partitioning problems run in 0(log n) time using 0(n) processors. Our algorithms are designed for the CREW PRAM model of parallel computation.

关键词： Parallel algorithms CREW PRAM Computational geometry Range searching partitioning algorithms L∞ and L1 metric B.3.2 [Shared Memory] C.1.2 [SIMD processor architecture] F.2.2 [Nonnumerical algorithms] G.1.0 [Parallel algorithms] 1.3.5 [Geometric algorithms] 1.5.3 [Pattern recognition algorithms]

来源：评论

学校读者我要写书评

暂无评论

An overview of stochastic partitioning algorithms and their performance

An overview of stochastic partitioning algorithms and their ...

引用

International Conference on Computer and Communication Engineering, ICCCE

作者： Ahlal Montaser M.E. Woodward Department of Computing University of Bradford UK

The main goals of quality-of-service (QoS) routing algorithms are: (1) to try to accommodate new connections which expect certain end-to-end QoS requirements and (2) to improve the overall network efficiency. These QoS requirements are in the form of delay, jitter, packet-loss and bandwidth. In order to accommodate every new connection through the network that satisfies the QoS, the resources must be controlled and reserved. However, there are issues related to scalability of QoS routing algorithms in large networks and the increased cost involved in terms of rapid computations. The problem of scaling QoS routing algorithms in the environment of large networks using partitioning is studied in this paper. In particular, the paper focuses on a review of the so called stochastic partitioning (SP) methods that dynamically change a network partition according to the traffic patterns in the network in order to minimise an objective function that reflects the computational effort involved in the underlying routing algorithms used in the network. Such methods therefore exploit the interactions between the network topology, the traffic flows and the routing which are not collectively considered by other forms of partitioning. Stochastic partitioning can be used to scale any routing algorithms so that the computational effort remains bounded to a manageable value as the number of network nodes grows. The performance is thus measured in terms of reduction in computational effort compared with non-partitioned networks.

关键词： Stochastic processes partitioning algorithms Routing Computer networks Telecommunication traffic Quality of service Delay Jitter Bandwidth Scalability

来源：评论

学校读者我要写书评

暂无评论

Adapting cache partitioning algorithms to pseudo-LRU replacement policies

Adapting cache partitioning algorithms to pseudo-LRU replace...

引用

International Symposium on Parallel and Distributed Processing (IPDPS)

作者： Kamil Kędzierski Miquel Moreto Francisco J. Cazorla Mateo Valero Barcelona Supercomputing Center (BSC) Technical University of Catalonia Barcelona Spain Spanish National Research Council (IIIA-CSIC) Barcelona Spain UPC and BSC Barcelona Spain

ISBN: (纸本)9781424464425

Recent studies have shown that cache partitioning is an efficient technique to improve throughput, fairness and Quality of Service (QoS) in CMP processors. The cache partitioning algorithms proposed so far assume Least Recently Used (LRU) as the underlying replacement policy. However, it has been shown that the true LRU imposes extraordinary complexity and area overheads when implemented on high associativity caches, such as last level caches. As a consequence, current processors available on the market use pseudo-LRU replacement policies, which provide similar behavior as LRU, while reducing the hardware complexity. Thus, the presented so far LRU-based cache partitioning solutions cannot be applied to real CMP architectures. This paper proposes a complete partitioning system for caches using the pseudo-LRU replacement policy. In particular, the paper focuses on the pseudo-LRU implementations proposed by Sun Microsystems and IBM, called Not Recently Used (NRU) and Binary Tree (BT), respectively. We propose a high accuracy profiling logic and a cache partitioning hardware for both schemes. We evaluate our proposals' hardware costs in terms of area and power, and compare them against the LRU partitioning algorithm. Overall, this paper presents two hardware techniques to adapt the existing cache partitioning algorithms to real replacement policies. The results show that our solutions impose negligible performance degradation with respect to the LRU.

关键词： partitioning algorithms Hardware Quality of service Throughput Sun Binary trees Logic Proposals Costs Degradation

来源：评论

学校读者我要写书评

暂无评论

Design and implementation of QoS-driven dynamic slot assignment and piconet partitioning algorithms over Bluetooth WPANs

Design and implementation of QoS-driven dynamic slot assignm...

引用

IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies

作者： C. Cordeiro S. Abhyankar D.P. Agrawal OBR Research Center for Distributed and Mobile Computing Department of ECECS University of Cincinnati Cincinnati OH USA

Bluetooth is a promising wireless technology aiming at supporting electronic devices to be instantly interconnected into short-range ad hoc networks. The Bluetooth medium access control protocol is based on the master/slave concept wherein any communication between slave devices has to go through the master. While this model is simple, it incurs longer delay between any two slave devices due to the use of non-optimal packet forwarding scheme and the use of double the bandwidth at the master. Moreover, if more than two devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast from the master. To handle these issues efficiently, we propose a novel combination of dynamic slot assignment (DSA) and piconet partitioning. With DSA, the piconet master dynamically assigns slots to slaves so as to allow them to communicate directly with each other without any intervention from the master. Such proposed communication architecture provides for quality of service (QoS) requests, admission control, and multi-device conversation by which a multicast-like communication is feasible within a piconet. To widen the scope of DSA, we propose QoS-driven enhanced DSA (EDSA) where dynamic piconet partitioning and scatternet support comes into picture. Devices are grouped in piconets according to their connection endpoints in EDSA, enabling it to be employed over a scatternet. We have performed extensive simulations and observe that these schemes drastically enhance Bluetooth performance in terms of delay and throughput, while significantly reducing network power consumption.

关键词： Algorithm design and analysis Personal area networks partitioning algorithms Bluetooth Master-slave Quality of service Scattering Ad hoc networks Media Access Protocol Access protocols

来源：评论

学校读者我要写书评

暂无评论

Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization 03

Multi-objective hypergraph partitioning algorithms for cut a...

引用

IEEE International Conference on Computer-Aided Design

作者： N. Selvakkumaran G. Karypis Department of Computer Science / Army HPC Research Center University of Minnesota Minneapolis USA Department of Computer Science University of Minnesota Minneapolis

ISBN: (纸本)9781581137620

In this paper we present a family of multi-objective hypergraph partitioning algorithms based on the multilevel paradigm, which are capable of producing solutions in which both the cut and the maximum subdomain degree are simultaneously minimized. This type of partitionings are critical for existing and emerging applications in VLSI CAD as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the ISPD98 benchmark show that our algorithms produce solutions that when compared against those produced by hMETiS have a maximum subdomain degree that is reduced by up to 35% while achieving comparable quality in terms of cut.

关键词： partitioning algorithms Minimization methods Iterative algorithms Permission Computer science Very large scale integration Integrated circuit interconnections Algorithm design and analysis Databases Information retrieval

来源：评论

学校读者我要写书评

暂无评论

Streaming Balanced Graph partitioning algorithms for Random Graphs 14

Streaming Balanced Graph Partitioning Algorithms for Random ...

引用

Annual ACM-SIAM Symposium on Discrete algorithms

作者： Isabelle Stanton Google Inc.

ISBN: (纸本)9781611973389

With recent advances in storage technology, it is now possible to store the vast amounts of data generated by cloud computing applications. The sheer size of `big data' motivates the need for streaming algorithms that can compute approximate solutions without full random access to all of the data. In this paper, we consider the problem of loading a graph onto a distributed cluster with the goal of optimizing later computation. We model this as computing an approximately balanced k-partitioning of a graph in a streaming fashion with only one pass over the data. We give lower bounds on this problem, showing that no algorithm can obtain an o(n) approximation with a random or adversarial stream ordering. We analyze two variants of a randomized greedy algorithm (looking at the distribution of edges from the vertex to be assigned, one prefers the partition that is the arg max and one that assigns the vertex proportional to the edge distribution) on random graphs with embedded balanced k-cuts and are able to theoretically bound the performance of each algorithms - the arg max algorithm is able to recover the embedded k-cut while the proportional variant can not. This matches the experimental results in [30].

关键词： Streaming ASSAY SCALE Storage technologies partitioning algorithms big data Line graph Random algorithms Arginine arg Lower bound

来源：评论

学校读者我要写书评

暂无评论

Parallelization of finite volume computations for heat transfer application using unstructured mesh partitioning algorithms

Parallelization of finite volume computations for heat trans...

引用

International Conference on High Performance Computing

作者： C. Singh Verma V.C.V. Rao Center for Development of Advanced Computing Pune University Campus Pune India Department of Computer Science University of Minnesota Minneapolis MN USA

An effective parallelization of finite volume computations for heat transfer application using unstructured triangular meshes and mesh partitioning algorithms are presented. The mesh partitioning software (METIS) is employed to create nearly load balanced subdomains and to minimize the interprocessor communications. Efficient data structures are developed to handle the neighboring element information at the interfaces of all subdomains and a simple strategy to overlap the computations to communications has been implemented for improving the performance of the program. The explicit time integration method is used and the results for the rectangular domain and L-shaped domain have been presented. The code (PHEAT2D) is written in Fortran90 and MPI for message passing is used. The algorithm is tested on distributed memory MIMD machine, PARAM OPENFRAME.

关键词： Concurrent computing Heat transfer Application software Temperature control partitioning algorithms Data structures Computer interfaces Algorithm design and analysis Parallel processing Equations

来源：评论

学校读者我要写书评

暂无评论

An evaluation of move-based multi-way partitioning algorithms

An evaluation of move-based multi-way partitioning algorithm...

引用

IEEE International Conference on Computer Design: VLSI in Computers and Processors, (ICCD)

作者： E. Yarack J. Carletta Silicon Graphics Inc. USA University of Akron USA

This paper presents a thorough analytical and experimental comparison of four move-based multi-way partitioning algorithms. Modifications are considered to the algorithm with the best solution quality, partitioning by free moves. These modifications allow a tradeoff to be made between solution quality and execution time. Results are given for ISCAS and other benchmarks.

关键词： partitioning algorithms Flexible manufacturing systems Simulated annealing Algorithm design and analysis Very large scale integration Silicon Graphics Design automation Application software Circuits

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：