Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer et al. · 2004
This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem. The associated clustering problem is as follows: Given n points in ℜd, find k points that minimize their average pairwise L1 distance. We present a natural approximation algorithm and show that it is a
Cited by 0
Baghbanbehrouzian, A., Goswami, D., Basten, A.A. et al. · TU/e Research Portal (Eindhoven University of Technology) · 2015
This work proposes a Multi-Constraint Resource Allocation (MuCoRA) method for applications from multiple domains onto multi-processors. In particular, we address a mapping problem for multiple throughput-constrained streaming applications and multiple latency-constrained feedback control applications onto a multi-processor platform running under a Time-Division Multiple-Access (TDMA) policy. The main objective of the proposed method is to reduce resource usage while meeting constraints from both these two domains (i.e., throughput and latency constraints). We show by experiments that the overall resource usage for this mapping problem can be reduced by distributing the allocated resource (i.e., TDMA slots) to the control applications over the TDMA wheel instead of allocating consecutive slots.
Cited by 0
Sotirios G. Ziavras, N.G. Haravu · IEE Proceedings - Computers and Digital Techniques · 1994
Modified hypercubes (MHs) have been proposed as building blocks for hypercube-based parallel systems that support the application of incremental growth techniques. In contrast, implementing the standard hypercube cannot be expanded in practice. However, processor allocation for MHs is a more difficult task due to a slight deviation in their topology from that of the standard hypercube. The paper proposes two strategies to solve the processor allocation problem for MHs. The proposed strategies are characterised by perfect subcube recognition ability and superior performance. Furthermore, two existing processor allocation strategies for standard hypercube networks, namely the buddy and free-list strategies, are shown to be ineffective for MHs, in the light of their inability to recognise many available subcubes. A comparative analysis that involves the buddy strategy and the new strategies is carried out using simulation results.
Cited by 0
S. Bani-mohammad, M. Ould-khaoua, I. Ababneh et al. · 2007
Two strategies are used for the allocation of jobs to processors connected by mesh topologies: contiguous allocation and non-contiguous allocation. In non-contiguous allocation, a job request can be split into smaller parts that are allocated possibly non-adjacent free sub-meshes rather than always waiting until a single submesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is increased. The extra communication overhead depends on how the allocation request is partitioned and assigned to free submeshes. This paper presents a new Non-contiguous allocation algorithm, referred to as Greedy-Available-Busy-List (GABL for short), which can decrease the communication overhead among processors allocated to a given parallel job. The GABL algorithm relies on a new approach that decomposes the allocation requests based on the sub-meshes available for allocation. This decreases the number of sub-meshes allocated to a job, hence decreases the distance traversed by messages, and which in turn decreases the communication overhead. In addition to allocation strategies, two job scheduling strategies, referred to as First-Come-First-Served (FCFS) and Shortest-Service-Demand-First (SSD) are studied, and they are used to compare the performance
Cited by 0
Xiaomei Zhu, Wei Lin · 2000
Cited by 1
Yu‐Chee Tseng · OhioLink ETD Center (Ohio Library and Information Network) · 1994
This dissertation consists of two parts. The first part considers the problem of arranging parallel algorithms in a parallel computer, which is typically modeled as the graph embedding problem. Conventionally, only the embedding of one guest graph to one host graph is considered. We study this problem for hypercubes in two new directions: multi-graph embedding and fault tolerance. A large number of graphs, including binary-reflected trees, Hamiltonian trees, binomial trees, binary trees, and meshes, are shown to be able to embed simultaneously into a hypercube with only a constant congestion. Some new fault-tolerant embedding of these graphs is also reported for an injured hypercube with faulty links. In particular, a highly resilient ring embedding algorithm is presented for embedding a ring of a given size in an injured hypercube with faulty nodes and links.
The second part presents some results for the interprocessor communication problem in multicomputer networks. An efficient parallel job migration algorithm is presented for a hypercube with buddy system as its allocation strategy and circuit switching or wormhole routing as its communication model. This algorithm can relieve the fragmentation problem effectively in that the routing is structure-preserving, adjacency-preserving, path-disjoint, and interference-free. A new trip-based model for multicast in a wormhole-routed network is proposed. The model is applicable to networks of any topology as long as two virtual channels are supported in each physical channel. It is shown how simple, adaptive, and distributed routing can be implemented with low cost.
Cited by 1Open access
Vitus J. Leung, David P. Bunde, P. W. Walker · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2012
Cited by 0
Rajesh K. Mansharamani, Mary K. Vernon · Minds at UW (University of Wisconsin) · 2007
The complexity of parallel applications and parallel processor scheduling policies makes both exact analysis and simulation difficult, if not intractable, for large systems. In this paper we propose a new approach to performance modeling of multiprogrammed processor scheduling policies, that of interpolation approximations. We first define a workload model that contains parameters for the essential properties of parallel applications with respect to scheduling discipline performance, yet lends itself to mathematical analysis. Key features of the workload model include general distribution of total job processing time, general distribution of available job parallelism, and a simple characterization of parallelism overheads. We then show that one can find specific values of the system parameters for which the parallel system under a given scheduling policy reduces to a queueing system with a known (closed-form) solution. Finally, interpolation between the points with known solutions is u...
Cited by 0Open access
Jens Mache, Virginia Lo · 1996
Resource management is a key area in the drive to fully realize the performance potential of parallel and distributed systems. For the task of assigning a set of processors of a massively parallel processing (MPP) system to a given job, various processor allocation strategies have been proposed in the research community and are in use at supercomputing sites. With the advent of the class of non-contiguous allocation strategies, the allocation performance bottleneck shifted from fragmentation to message-passing contention. This paper presents a method to estimate and minimize contention incurred by noncontiguous allocation strategies. Our approach is to analyze the spatial layout of dispersed nodes. Our contribution is a set of dispersal metrics that predict contention well and that are efficient to implement for a variety of interconnection topologies. We put the dispersal metrics to the test by comparing their contention estimates with measurements taken from a message-pass...
Cited by 0
Allen B. Downey · Lecture notes in computer science · 1997
Cited by 99
Ancona F, ZUNINO, RODOLFO · CINECA IRIS Institutial Research Information System (University of Genoa) · 1997
Cited by 0
Allen B. Downey · 1997
Cited by 9
César A. F. De Rose · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 1993
Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente, a fim de evitar uma rápida fragmentação do cubo e de não exceder o tempo máximo de espera de uma determinada aplicação. A partir dos algoritmos propostos é apresentada a definição de um servidor de processadores para o compartilhamento de uma máquina multiprocessadora hipercúbica em uma rede de estações de trabalho. Algumas funções deste servidor são implementadas por um protótipo denominado Sub-Cube RPC. Com o objetivo de analisar o comportamento da rede de estações em relação a inclusão de um novo recurso a ser compartilhado, foi desenvolvido, juntamente com o grupo de Avaliação de Desempenho ADMP, um simulador para o ambiente SUN/UNIX. Através desta ferramenta e dos tempos de resposta obtidos pelo protótipo do servidor desenvolvido é possível avaliar o custo que o tráfego gerado pelo servidor adiciona à rede, sendo possível a manipulação de parâmetros da rede e do servidor. Os resultados obtidos nas versões paralelas implementadas são comparados com o desempenho das versões seqüenciais. Para viabilizar esta comparação, todos os algoritmos seqüenciais encontrados na literatura também foram implementados na linguagem "C" no ambiente alvo UNIX e encontram-se em anexo. As versões paralelas foram implementadas utilizando-se recursos da própria rede de estações, através de diretivas socket, e também em Transputers na linguagem C paralela. O protótipo do servidor de processadores foi implementado como um servidor RPC para uma rede de estações UNIX também na linguagem "C". A ferramenta de simulação para o funcionamento do servidor foi implementada na linguagem "C" e seu sistema de entrada de dados e visualização utiliza a interface X-Windows. Com os resultados deste trabalho se pode ter uma boa idéia dos efeitos e das dificuldades encontradas na paralelização dos algoritmos de alocação e gerência de processadores para máquinas Hipercúbicas. As informações contidas no trabalho auxiliam na melhoria do tempo de resposta dos algoritmos seqüenciais atuais e no desenvolvimento de novos algoritmos com mais recursos e ainda assim viáveis em ambientes interativos, graças a utilização de paralelismo. O protótipo Sub-Cube RPC demonstra como os algoritmos estudados neste trabalho podem ser aplicados na construção de um servidor de processadores para máquinas multiprocessadas. O protótipo servirá como base para a implementação de um servidor semelhante no CPGCC/UFRGS, que colocará uma placa de Transputers à disposição da rede de estações do grupo de processamento paralelo.
Cited by 0Open access
Kimberly M. Wasserman A, George Michailidis B, Nicholas Bambos C · 2004
In this paper, we study the problem of dynamic allocation of the resources of a general parallel processing system, comprised of M heterogeneous processors and M heterogeneous traffic flows. Each traffic flow is modeled as a Bernoulli sequence of binary random variables, with the arrival rate depending on the job class. The service times of the jobs are independent random variables with distributions that depend on both the job class and the processor class. We characterize the stability region for this system and introduce a processor allocation policy that stabilizes the system under the maximum possible traffic loadings. We also investigate some special cases of this model and finally characterize its performance in the presence of finite buffers. © 2004 Elsevier B.V. All rights reserved.
Cited by 0
Haran Boral, David J. DeWitt · ACM Transactions on Database Systems · 1981
In this paper four alternative strategies for assigning processors to queries in multiprocessor database machines are described and evaluated. The results demonstrate that SIMD database machines are indeed a poor design when their performance is compared with that of the three MIMD strategies presented. Also introduced is the application of data-flow machine techniques to the processing of relational algebra queries. A strategy that employs data-flow techniques is shown to be superior to the other strategies described by several experiments. Furthermore, if the data-flow query processing strategy is employed, the results indicate that a two-level storage hierarchy (in which relations are paged between a shared data cache and mass storage) does not have a significant impact on performance.
Cited by 46Open access
2008
An adaptively parallel job is one in which the number of processors that can be used without waste varies during execution. This paper presents the design and implementation of a dynamic processorallocation system for adaptively parallel jobs. We focus on the specific case of parallel jobs that are scheduled with the randomized work-stealing algorithm, as is used in the Cilk multithreaded language. The jobs are run on a shared-memory symmetric multiprocessor (SMP) system. We begin by presenting a simple heuristic for estimating the processor desire of a Cilk job, based on the number of incomplete Cilk procedure frames queued on each of the job’s processors. Then, we show how these estimates can be used to allocate processors to multiple running Cilk jobs in a fair and efficient way. We present empirical evidence verifying the correctness of our dynamic processor-allocation system and evaluating its overhead. 1 1
Cited by 0
A. P. Mullery, Graham C. Driscoll · Communications of the ACM · 1970
A scheduling algorithm is proposed which is intended to minimize changes of tasks on processors and thereby reduce overhead. The algorithm also has application to more general resource allocation problems. It is implemented by means of a method for efficiently handling dynamically changing segmented lists.
Cited by 11Open access
Jurij Silc, Borut Robic · 2007
Many processor allocation methods for two-dimensional mesh connected parallel computers have been proposed in the literature. Generally, allocation methods can be divided into two categories, first-fit and best-fit. Assume that a mesh can be dynamically partitioned into several submeshes each of which can be concurrently allocated to one of the incoming independent programs and, after completion of that program, reclaimed by the system for future use. A first-fit allocation methods allocates the incoming programs to the first free submesh it detects. A best-fit methods identifies several candidate submeshes, and the program is allocated to the best-fit candidate based on certain heuristic. In this paper, we describe and evaluate a new best-fit processor allocation method called Weighted Bipartite Matching Allocation (WBMA) that, combined with a static optimizing mapping, reduces mesh system fragmentation and improves system's throughput.
Cited by 0
Su-Hui Chiang, Mary K. Vernon · Lecture notes in computer science · 1996
Cited by 35
Agrawal, Rajeev, Mansharamani, Rajesh K, Vernon, Mary K · Minds at UW (University of Wisconsin) · 1993
. The first result of this paper is a lower bound on mean response time, under a very general workload model, per class of multiprogrammed parallel processor allocation policies. This bound is derived from the mean response time of the optimal uniprocessor scheduling policy that uses the same workload information as the class of parallel processor allocation policies. The derivation of the bound also suggests how tighter bounds can be obtained on a per policy basis in some cases. Key features of the workload model include general job demands, available parallelisms, execution rates, and inter-arrival times, with arbitrary dependencies among these workload variables. The second result is that for linear execution rates (i.e., perfect speedups) and for i.i.d. exponential job demands that are independent of everything else, the Preemptive Smallest Available Parallelism First policy is optimal among policies that use no explicit information about job demand. Likewise, among all processor c...
Cited by 1Open access