The creation of virtual machines (VMs) is one of the procedures of resource scheduling which is the key technology in cloud computing systems. Currently it is rarely studied independently, and it is always set as a static model where the number and the type of VMs are predefined before scheduling. However, with the static model, it is difficult to consider the overall optimization for the scheduling and it is not user-friendly because of users' imprecise requirements. Therefore, in this paper a dynamic model for VMs' creation is proposed. With this model, users only submit fuzzy requirements for computing resources, while the necessary number and type of VMs are calculated according to the current environment and dynamically created for further scheduling. The model is implemented in CloudSim, where the key technologies are presented. Analysis and experiments were carried out to verify the extension of the model in a more wide research area, such as resource scheduling for multi-objective optimization and scheduling tasks with priorities.

One of the most important steps in obtaining a relational model from legacy systems is the extraction of functional dependencies (FDs) through data mining techniques. Several methods have been proposed for this purpose and most use direct search methods that traverse the search space in exponential time in the number of attributes of the relation. As it is not uncommon to find in practice relations with tens of attributes, a need exists to further develop more efficient techniques to find FDs. The method studied here finds the minimal set of minimal FDs using algorithms that solve the hypergraph duality problem applied on the complement of the refutation hypergraph of the relation without going through the exponential search space. After showing that the extraction of FDs can be reduced to the hypergraph duality problem, experimental results are given as verification and characterization of the correctness and time complexity of the proposed tool.

Virtualization has proven to be a powerful technique used for resource partitioning and resource aggregation. Although this concept has been widely utilized in cluster computing, distributed systems and system consolidation; it has not been equally applied to improve performance of commodity operating systems and applications. This paper introduces a client-driven paradigm for harnessing specific system components and presenting them to the operating system as local devices (virtual devices). This client-driven approach based on the transparent remote execution environment (TREx) not only allows for systems inside a network to share individual resources such as memory, graphics cards or co-processors, but is also completely transparent to users, applications and operating systems. Additionally, this paper presents specific architectural designs necessary for achieving maximum performance with these virtual devices, and presents the implementation of two of them: a distributed ramdisk and a distributed graphics device.

This paper provides a framework for dynamic adaptive computing in heterogeneous clusters for computationally intensive applications. The framework considers a set of discoverable interconnected computational resources and either a parallel or sequential workload needing to be executed. An adaptive inclusion/exclusion algorithm is used to select the resources by using novel performance measurements and profiling techniques. Furthermore, contrary to a greedy approach where all the resources are seized for the workload application, our framework only harnesses the best fit resources measured against system-wide performance characterization, and is contingent upon the current workload definition. The intelligent selection of a subset of resources has proven to achieve better performance; especially in environments with a high level of heterogeneity where the characteristics of some resources may not achieve the best performance the cluster can provide. Additionally, this paper provides a novel analysis of the workload and cluster characteristics, exhibiting analytical starting points to be used in the resource selection.

We introduce a computational framework for concurrent adaptive computing in heterogeneous environments for computationally intensive applications. This framework considers the presence of inter-connected computational resources which are discoverable and a workload which needs to be executed either by concurrent means or on a singular resource. The selection of resources, using a novel measurement of performance, leads to the adaptive inclusion/exclusion of resources to be used in the efficient execution of workload computations. The adaptive approach is that it makes a determination to include a proper subset of resources for system inclusion to execute a workload, which is contrary (except when the subset is all-inclusive) to a greedy approach where all the resources are seized for the workload application. The selection of a subset of resources may be more efficient due to the high level of heterogeneity of the resources, where, for some resources, certain resource selections may be detrimental or have no value to send work there. Furthermore, this framework aims to lessen the unpredictability and uncontrollability of heterogeneous systems by using this analysis for resource selection.

Clusters of Computers have become a cost-effective alternative for parallel and distributed computing systems processing computationally intensive tasks. Normally, clusters are composed of high performance computational nodes linked together by low-latency, high-bandwidth interconnection networks. With the advent of modern optical networking technologies, latency in long-distance links is close to that of local-area links. By using Service Address Routed (SAR) optical networks, NEOS-based clusters can be used transparently as single, tightly-coupled clusters of computers, regardless of the distance between their components while keeping a simple service-oriented interface. A performance-wise analysis of such clusters is presented in this work.

Due to the increasing complexity of scientific models, large-scale simulation tools often require a critical amount of computational power to produce results in a reasonable amount of time. For example, multi-system wireless network simulations involve complex algorithms of traffic balancing and communication control on large geographical areas. Moreover many of these intensive applications are designed for single sequential machines and large sums of money are spent on purchasing powerful servers that can give results in a satisfactory amount of time. The aim of this paper is to introduce a general-purpose tool, dubbed transparent remote execution (TREx), which avoids resorting to expensive servers by providing a cost effective, high performance, distributed solution. TREx is a daemon that dynamically exploits idle operational in-use workstations. Based on elaborate rules of computational resource management, this daemon permits a master to scan workstations within a predefined subnetwork and share the workload among the least occupied processing elements. It also provides a clear framework for parallelization that applications can exploit. By providing a simple way of federating computational resources, such a framework could drastically reduce hardware investments.

Selection of spaceborne computing platforms requires balance among several competing factors. Traditional performance analysis techniques are ill-suited for this purpose due to their overriding concern with runtime. The suitability measure is a new approach that quantifies the match between a computing platform and a program. It analyzes a program at the opcode and control flow levels, and compares this to a machine's capability to support the unique characteristics of the program. In this paper we develop the suitability measure and a series of program analysis methods. Experimental results confirm that machines that provide a better match to the program yield a higher suitability score. We prove that loops provide the only contribution to the suitability value, and also that the number of loop iterations is irrelevant, leading to the conclusion that a single pass through a loop is sufficient to derive a suitability value.

A working single system image distributed operating system is presented. Dubbed Kerrighed, it provides a unified approach and support to both the MPI and the shared memory programming models. The system is operational in a 16-processor cluster at the Institut de Recherche en Informatique et Systemes Aleatoires in Rennes, France. In this paper, the system is described with emphasis on its main contributing and distinguishing factors, namely its DSM based on memory containers, its flexible handling of scheduling and checkpointing strategies, and its efficient and unified communications layer. Because of the importance and popularity of data parallel applications in these systems, we present a brief discussion of the mapping of two well known and established data parallel algorithms. It is shown that ShearSort is remarkably well suited for the architecture/system pair as is the ever so popular and important two-dimensional fast Fourier transform. (2D FFT).

In this paper we propose a new class of scheduling policies, dubbed Concurrent Gang, that combines the advantages of gang scheduling for communication and synchronization intensive parallel jobs with the flexibility of a Unix scheduler for sequential and I/O intensive jobs. Besides that, scalability in Concurrent Gang is achieved through the use of a global synchronizer that coordinates the gang scheduler among different processors. Simulation results are provided comparing the performance of Concurrent Gang with Gang Scheduling and show significant performance improvements, in particular for I/O bound jobs.

Benchmarking is a widely used approach to measure computer performance. Current use of benchmarks only provides running times to describe the performance of a tested system. Glancing through these execution times provides little or no information about system strengths and weaknesses. A novel benchmarking methodology is proposed to identify key performance parameters; the methodology is based on measuring performance vectors. A performance vector is a vector of ratings that represents delivered performance of primitive operations of a system. In order to measure performance vectors, a geometric model is proposed which defines system behavior using the concepts of support points, context lattice, and operating points. In addition to the performance vector, other metrics derivable from the geometric model include the variation in system performance and the compliance of benchmarks. Using this methodology, the performance vectors of the Sun SuperSPARC (desktop workstation) and the Cray C90 (vector supercomputer) are evaluated using the SPEC benchmarks and the Perfect Club, respectively. The proposed methodology respects several practical constraints and issues in benchmarking. The instrumentation required is minimal. The benchmarks used are realistic (not synthetic) in order to reflect the delivered (not peak) performance. Finally, operations in the performance vector are not measured individually since there may be significant interplay in their executions.

A dynamic two-stage Delta network (N inputs and outputs) is introduced and analyzed for permutation routing. The notion of evil twins is introduced and a deterministic procedure is given to route any permutation in no more than 2/sup 4//spl radic/N network cycles. Two limited randomized routing schemes are then analyzed. The first called Single Randomization yields on average at most N!+1 (N!=O(logN/loglogN)/sup 1/ and is the greatest integer such that (N!)!/spl les/N) network cycles and the second called Multiple Randomization yields on average at most upper bound [log(logN+1)]+2+1/N network cycles for any input permutation. The probability of any permutation requiring at least c network cycles more than the above average bounds is then shown to be at most 1/(c+1) for Single Randomization and 1/N/sup r/ for Multiple Randomization, respectively. It is then shown how the dynamic two-stage network can be physically realized as a three-stage network. Both the evil twin and Multiple Randomization algorithms have been integrated into an off-the-shelf ASIC from PMC-Sierra, Inc. (PM-73488) which has been designed as a building block for such a three-stage implementation. These routing schemes are also adapted to run on a recirculating network. Recirculation is used to effect a reshuffling of data as in the dynamic network, but with a considerable reduction in network cost.

Benchmarking is a widely used approach to measure computer performance. Current use of benchmarks only provides running times to describe the performance of a tested system. Glancing through these execution times provides little or no information about system strengths and weaknesses. A novel benchmarking methodology is proposed to identify key performance parameters; the methodology is based on measuring performance vectors. A performance vector is a vector of ratings that represents delivered performance of primitive operations of a system. Measuring the performance vector of a system in a typical user workload can be a tough problem. We show how the performance vector falls out of an equation consisting of dynamic instruction counts and execution times of benchmarks. We present a non-linear approach for computing the performance vector. The efficacy of the methodology is ascertained by evaluating the micro-architecture of the Sun SuperSPARC superscalar processor using SPEC benchmarks. Results show interesting tradeoffs in the SuperSPARC and speak favorably of our methodology.

Two hardware barrier synchronization schemes are presented which can support deep levels of control nesting in data parallel programs.Hardware barriers are usually an order of magnitude faster than software implementations.Since large data parallel programs often have several levels of nested barriers, these schemes provide significant speedups in the execution of such programs on MIMD computers.The first scheme performs code transformations and uses two single-bit-trees to implement unlimited levels of nested barriers.However, this scheme increases the code size.The second scheme uses a more expensive integer-tree to support an exponential number of nested barriers without increasing the code size.Using hardware already available on commercial MIMD computers, this scheme can support more than four billion levels of nesting.

Diffusion is a well-known algorithm for load-balancing in which tasks move from heavily-loaded processors to lightly-loaded neighbors. This paper presents a rigorous analysis of the performance of the diffusion algorithm on arbitrary networks.

We analyze a generalization of the traditional delta network, dubbed Expanded Delta Network (EDN), which provides multiple paths that can be exploited to reduce contention. In massively parallel SIMD computers, the trend is to put a large number of processors on a chip, but due to I/O constraints only a subset of the processors may have access to the network at any time. This leads to the Restricted Access Expanded Delta Network of which the MasPar MP-1 router network is an example.

A simple but powerful architecture based on the classical associative processor model is proposed. By distributing logic among slices of storage cells such that a number of bit-planes share a simple logic unit, bit-parallel arithmetic for massively parallel processing becomes feasible. For m-bit operands, this architecture enables complex operations such as multiplication and division to execute in O(m) cycles as opposed to O(m/sup 2/) for bit-serial machines. Algorithms which utilize this bit-parallel property to efficiently perform operations on floating point data have been developed. The simplicity of the architecture enables its implementation using VLSI technology, and hence allows the construction of a word-parallel, bit-parallel, massively parallel (P/sup 3/) computing system. Implementations of the fast Fourier transform and matrix multiplication are presented to illustrate the operation of this system.>

A sorting algorithm, dubbed MeshSort, for multidimensional mesh-connected multiprocessors is introduced. Bitonic Sort and ShearSort are shown to be special cases of MeshSort. MeshSort thus provides some insight into the operation of parallel sorting. It requires operations only along orthogonal vectors of processors, simplifying the control of the multiprocessor. This allows MeshSort to be used on any reduced architecture where a multidimensional memory structure is interconnected with a lower dimensional structure of processors. A modified version of MeshSort, called FastMeshSort, is presented. This algorithm applies the same basic principle as MeshSort, and is almost as simple to implement, but achieves much better performance. The modified algorithm is shown to be very efficient for reasonably sized meshes. FastMeshSort is presented as a practical sorting and routing algorithm for real multidimensional mesh-connected multiprocessors. The algorithms can easily be extended to other multiprocessor structures.>

A graph theoretical representation for a class of interconnection networks is suggested. The idea is based on a definition of orthogonal binary vectors and leads to a construction rule for a class of orthogonal graphs. An orthogonal graph is first defined as a set of 2/sup m/ nodes, which in turn are linked by 2/sup m-n/ edges for every link model defined in an integer set Q*. The degree and diameter of an orthogonal graph are determined in terms of the parameters n, m, and the number of link modes defined in Q*. Routing in orthogonal graphs is shown to reduce to the node covering problem in bipartite graphs. The proposed theory is applied to describe a number of well-known interconnection networks such as the binary m-cube and spanning-bus meshes. Multidimensional access (MDA) memories are also shown as examples of orthogonal shared memory multiprocessing systems. Finally, orthogonal graphs are applied to the construction of multistage interconnection networks. Connectivity and placement rules are given and shown to yield a number of well-known networks.>

The shuffle-exchange network can be generalized by the definition of three parameters (n, r', k). In a generalized shuffle-exchange (GSE) network, 2/sup n/ inputs are first permuted by a shuffle such that an n-bit source address label is rotated left r'-bit positions to yield the destination address label. The exchange performs arbitrary permutations on 2/sup k/*2/sup k/ exchange switches. The GSE networks can emulate a variety of other networks, including orthogonally connected multidimensional cubes of all sizes, and they provide the possibility of incorporating alternate paths into networks without the addition of extra processing nodes or interconnections. Generalized shuffle-exchange networks are characterized herein by their connectivity, their diameter, and the number of alternate paths they permit.>

The gradual refinement of a general approach to two-dimensional sorting, the shear-sort algorithm, to more sophisticated and specialized sorting algorithms on mesh-connected computers is described. The analysis of the shear-sort algorithm gives rise to a novel perspective of two-dimensional sorting, which seems to be a very powerful tool for developing efficient algorithms. The same methods can be extended for sorting in higher dimensions, for example, in the three-dimensional mesh. The concept of clean and dirty rows can be modified to clean and dirty planes (or hyperplanes for dimensions greater than three). Although only two schemes (purely recursive and iterative) are explicitly described, the reader may construct his own algorithm using similar technique and slight modifications. Designing an O(n) algorithm for sorting on a mesh becomes much simpler using the techniques developed.>

A novel implementation is presented, the Stubborn protocol, which provides the right compromise to obtain a balanced and near-optimal performance under both normal (control) operation and transient (emergency) conditions. It is based on the following simple principle: stations make access attempts as in the usual 1-persistent CSMA/CD (carrier-sense multiple-access with collision detection). In case of collision, a station with priority higher than zero will not interrupt transmission, but will exercise its right to extend the collision for a period proportional to its priority level. The station that persists longer will be able to start 'clean' transmission as soon as all others have desisted. The algorithm is complemented with tie-breaking procedures.>

An Orthogonal Memory Access system allows a multiplicity of processors to concurrently access distinct rows or columns of a rectangular array of data elements. The resulting tightly-coupled multi-processing system is feasible with current technology and has even been suggested for VLSI as a “reduced mesh”. In this paper we introduce the architecture and concentrate on its application to a number of basic vector and numerical computations. Matrix multiplication, L-U decomposition, polynomial evaluation and solutions to linear systems and partial differential equations, all show a speed-up of 0(n) for a n-processor system. The flexibility in the choice of the number of PEs makes the architecture a strong competitor in the world of special-purpose parallel systems. Actually, we prove that the machine exhibits the same performance as any other system with the same number of processors within a factor of 3.

In this paper, We consider the problem of sorting n2 numbers, initially distributed randomly in an n × n mesh-connected processor array with one element per processor. We show a lower bound, based on distance arguments, of 4n routing steps on mesh-connected processors operating in an SIMD mode with no wraparounds in rows or columns, We present an algorithm using a novel approach, which is optimal upto the conslant of the leading term, and hence, succeed in proving the tightness of the lower bound based on distance. Keeping in mind the practical difficulties in implementation of this algorithm, we also present an extremely practical O(n) algorithm amenable for VLSI implementation and for existing mesh- connected computers. All the results in this paper were derived by using a new method of analysis inspired by the discovery of shear-sort or row-column sort.

Multi-operand associative techniques attain their full power in algorithms Where the data may be recast into disjoint data sets, all acted upon concurrently, each by a different operand common to the set. But the multi-operand approach can also serve to enhance arithmetic operations significantly. The speed-up of associative multiplication by handling a number of multiplier bits at a time is described and analyzed, including an effective algorithm for a limited sum of products. The most complex process treated is convolution, which serves to illustrate the enhancement of an extended sum of products. Any number of vectors stored in memory can be convolved simultaneously by a common filter vector. Execution time is 45 milliseconds for 1024 element data and filter vectors, 2048 element results, and l6-bit precision.