Search

The travelling salesman problem (TSP) is a well-known NP-hard problem. It is difficult to efficiently find the solution of TSP even with the large number of gene instances. Evolutionary approaches such as genetic algorithm have been widely applied to explore the huge search space of TSP. However, the feasibility constraints of TSP make it difficult to devise an effective crossover method. In this paper, we propose an improved constructive crossover for TSP. As the performance of graphics processing units (GPUs) rapidly improves, GPU-based acceleration is increasingly required for complex computation problems. Unfortunately, the constructive crossover methods cannot be easily implemented in a parallel fashion because each gene element of offspring is dependent on the previous element in the gene string. In this paper, we propose a more effective method with which large number of genes can evolve effectively by exploiting the parallel computing power of GPUs and an effective parallel approach to genetic TSP where crossover methods cannot be easily implemented in parallel fashion. [ABSTRACT FROM AUTHOR]

Given a massive set of records, similarity join is to find pairs of records with similarity score greater than a threshold. In this paper, we address the problem of scaling up similarity join for general metric distance functions using MapReduce. First, we propose a novel index structure, Similarity Join Tree (SJT), which partitions data based on the underlying data distribution, and distributes similar records to the same group. Different from existing approaches, SJT can prune a large number of comparisons within reduce tasks by utilizing the by-product results generated in partitioning data. Then, to avoid the straggler reduce tasks, we design a graph partition algorithm by extending the well known Fiduccia-Mattheyses algorithm which can ensure load balancing while minimizing communication cost and redundancy in all reduce tasks. Experimental results using real data sets show that our approach is more effective and scalable compared to state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

With introduction of dynamic voltage scaling techniques, promising results have been obtained for minimizing overall power consumptions of the real-time systems by exploiting the hardware characteristics of latest processors. Traditionally, preemptive systems have been investigated in depth and interesting results are established accordingly. The non-preemptive counterpart, though equally important, has received very little attention. Due to its simple implementation and lesser number of context switching, non-preemptive systems offer even more opportunities to be exploited for reducing power consumption of the system. In this paper, we establish mathematical foundations for determining the system speed appropriate to non-preemptive nature of tasks such that the timing constraints remain intact and overall power consumption is reduced. We compare our results with closely related techniques, and our analysis shows that the reduction in power consumptions is significant with proposed technique. [ABSTRACT FROM AUTHOR]

Modern systems present complex memory hierarchies and heterogeneity among cores and processors. As a consequence, efficient programming is challenging. An easy-to-understand performance model, offering guidelines and information about the behaviour of a code, may be useful to alleviate these issues. In this paper, we present two extensions of the well-known Berkeley Roofline Model. The first of these extensions, the Dynamic Roofline Model (DyRM), takes into consideration the complexities of multicore and heterogeneous systems, offering a more detailed view of the evolution of the execution of a code. The second, the 3DyRM, also adds information about the latency of memory accesses to better represent the behaviour on systems with complex memory hierarchies. A set of tools to obtain and represent the models has been implemented. These tools obtain the needed data from hardware counters, with low overhead. Different views are displayed by the tool that can be used to extract the main features of the code. Results of studying, with these tools, the NAS Parallel Benchmarks for OpenMP on two different systems are presented. [ABSTRACT FROM AUTHOR]

During the last few years, the availability of hardware accelerators, such as GPUs, has rapidly increased. However, the entry cost to GPU programming is high and requires a considerable porting and tuning effort. Some research groups and vendors have made attempts to ease the situation by defining APIs and languages that simplify these tasks. In the wake of the success of OpenMP, industria and academia are working toward defining a new standard of compiler directives to leverage the GPU programming effort. Support from vendors and similarities with the upcoming OpenMP 4.0 standard lead us to believe that OpenACC is a good alternative for developers who want to port existing codes to accelerators. In this paper, we evaluate three OpenACC implementations: two commercial implementations (PGI and CAPS) and our own research implementation, accULL, to evaluate the current status and future directions of the standard. [ABSTRACT FROM AUTHOR]

Load balance is an important issue for the performance of software distributed shared memory (DSM) systems. One solution of addressing this issue is exploiting dynamic thread migration. In order to reduce the data consistency communication increased by thread migration, an effective load balance scheme must carefully choose threads and destination nodes for workload migration. In this paper, a group-based load balance scheme is proposed to resolve this problem. The main characteristic of this scheme is to classify the overloaded nodes and the lightly loaded nodes into a sender group and a receiver group, and then consider all the threads of the sender group and all the nodes of the receiver group for each decision. The experimental results show that the group-based scheme reduces more communication than the previous schemes. Besides, this paper also resolves the problem of the high costs caused by group-based schemes. Therefore, the performance of the test programs is effectively enhanced after minimizing the communication increased by thread migration. [ABSTRACT FROM AUTHOR]

Scheduling jobs dynamically on processors is likely to achieve better performance in multiprocessor and distributed real-time systems. Exhaustive methods for determining whether all jobs complete by their deadlines, in systems that use modern priority-driven scheduling strategies, are often infeasible or unreliable since the execution time of each job may vary. We previously published research results on finding worst-case bounds and efficient algorithms for validating systems in which independent jobs have arbitrary release times and deadlines, and are scheduled on processors dynamically in a priority-driven manner. An efficient method has been proposed to determine how late the completion times of jobs can be in dynamic systems where the jobs are preemptable and nonmigratable. This paper further presents the performance characteristics of the proposed methods, and shows its soundness by providing extensive simulation results. The worst-case completion times of jobs obtained with the proposed methods are compared with the values by simulations under different workload characteristics. The simulation results show that the proposed algorithm performs considerably well for diverse workloads. Considering the previous work showed the unlikelihood of finding tighter bounds than the one given in the paper, the simulation results indicate that the proposed methods effectively constitute a theoretical basis needed for a comprehensive validation strategy that is capable of dealing with dynamic distributed real-time systems. [ABSTRACT FROM AUTHOR]

One of the main limitations of existing monitoring systems is their dependency on the continuous recording of video data. As a result, the system consumes huge power and needs large memory to store this data. The aim of this paper is to present an automated monitoring system that can save memory, as well as measure the target distance precisely based on the motion sensors and ultrasonic sensor. The target is detected by motion sensors and then an ultrasonic sensor is used to measure the target distance. The cross-correlation technique is used to calculate the distance of targets using ultrasonic signal. To obtain high measuring accuracy, noise reduction technique and temperature effect on velocity have been adopted. A series of real-world experiments are conducted with different targets and target positions. The experimental results show that using a noise reduction technique and temperature compensation improve the accuracy of the designed system. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the authors discuss various reports on topics including paradigms and applications for ultrascale systems in computers, computer programming and software and runtimes enhancements.

Cloud computing has gradually evolved into an infrastructural tool for a variety of scientific research and computing. It has become a trend that lots of products have been migrated from local servers to cloud by many institutions and organizations. One of the challenges in cloud computing now is how to run software efficiently on cloud platforms since lots of original codes are not capable of being executed in parallel on cloud contexts, resulting in that the power of clouds cannot be exerted well. It is costly to redesign and convert current sequential codes into cloud platform. Thus, automatic translation from sequential code to cloud code is one of the directions that could be taken to resolve the problem of code migration in cloud infrastructure. In this paper, a new Java to MapReduce (J2M) translator is developed to achieve the automatic translation from sequential Java to cloud for specific data-parallel code with large loops. This paper will provide details about the design of our translator and evaluate our performance through experiments. The experimental results not only indicate that the translator can precisely translate the sequential Java into cloud codes, but also show that it can achieve very good speedup in performance, and we expect that an almost linear speedup is possible if larger enough data is processed. It is believed that the J2M translator is an ideal stereotype for code migration and will play an important role in the transition era of cloud computing. [ABSTRACT FROM AUTHOR]

Program code is at risk from a wide range of attack vectors that appear at various stages during the compilation and execution of machine code. The existing approaches for detecting threats in program code have many restrictions in terms of their functionality and the types of threats that can be identified. The paper proposes an approach for detecting timing channels in program code based on just-in-time compilation in a virtual execution environment. Annotations of code permit the management of analyses and transformations. The virtual environment uses both static and dynamic analyses of the intermediate representation of the code and re-compiles such code to be safe. The language of annotations allows us to formulate rules for the detection of timing channels and to manage the amount of time spent on such analyses by adapting the precision of these analyses. The results demonstrate that unlike static compilation of program code, our approach dynamically analyses and transforms large sizes of code in real time. They also demonstrate that the virtual execution environment that uses the proposed approach is efficient. [ABSTRACT FROM AUTHOR]

In this paper, a dual-mode routing approach is proposed for routing messages in 2D photonic network on chip (NoC) platforms. The dual-mode routing approach is based on selecting exclusively one of two routing techniques for each stage of a parallel application. Depending on the data exchange requirements of a specific stage of an application, either a conventional per-message-based routing or a collective routing technique is selected, and the network on chip architecture is organized to support that selection. The network on chip architecture that we use is a two-dimensional torus topology built from novel $$8\times 8$$ non-blocking all-port photonic switches. The design of $$8\times 8$$ non-blocking all-port photonic switch empowers each node with simultaneous connections to four other nodes in the network. The rich connectivity provided by the switches helps the collective routing technique to efficiently support collective communication operations by allowing deadlock-free and contention-free dense data exchange among the nodes. Similar dense data exchanges are also required for some commonly known parallel algorithms such as parallel matrix multiplication, linear equation solvers and n-body simulation algorithms, just to name a few. A lightweight electronic network is employed for establishing and tearing down the photonic communication paths (light paths) in per-message-based routing technique. The lightweight electronic network is also used for coordinating the whole network in the collective routing technique. [ABSTRACT FROM AUTHOR]

In large-scale supercomputers, the interconnection network plays a key role in system performance. Network topology highly defines the performance and cost of the interconnection network. Direct topologies are sometimes used due to its reduced hardware cost, but the number of network dimensions is limited by the physical 3D space, which leads to an increase of the communication latency and a reduction of network throughput for large machines. Indirect topologies can provide better performance for large machines, but at higher hardware cost. In this paper, we propose a new family of hybrid topologies, the k-ary n-direct s-indirect, that combines the best features from both direct and indirect topologies to efficiently connect an extremely high number of processing nodes. The proposed network is an n-dimensional topology where the k nodes of each dimension are connected through a small indirect topology of s stages. This combination results in a family of topologies that provides high performance, with latency and throughput figures of merit close to indirect topologies, but at a lower hardware cost. In particular, it doubles the throughput obtained per cost unit compared with indirect topologies in most of the cases. Moreover, their fault-tolerance degree is similar to the one achieved by direct topologies built with switches with the same number of ports. [ABSTRACT FROM AUTHOR]

Service discovery is known as one of the fundamental components in vehicular networks. Intelligent transportation systems performance improves by the availability of efficient service discovery solutions in vehicular networks. Nonetheless, some challenges such as network partitioning and vehicular congestion reduce the efficiency of these components. Additionally, most of the presented solutions are suffering from the low query success rate and high overhead of service information updates. A proper framework has been presented in this paper for the optimal service discovery in an urban area. Considering related framework, a binary integer programming model has been proposed for optimal infrastructure placement in urban areas and a peer-to-peer (P2P) network which is created on infrastructure nodes. The query success rate and overheads of updating service information improved by benefits of P2P network and infrastructure nodes. In framework evaluation, an Infrastructure-based location service discovery mechanism has been presented in urban areas. The simulation results showed an improvement in performance of the given solution in comparison with the most recent other solutions. [ABSTRACT FROM AUTHOR]

Efficient resource discovery plays a vital role in the effective management of resources and applications in heterogeneous computing environments. Therefore, the knowledge of applications' behavior and resources' usage pattern improves resource discovery decisions. This knowledge can be provided for the resource discovery mechanism by cooperating with the load balancing mechanism. In this paper, we formulate their cooperation by considering some parameters that represent applications' behavior and resources' usage patterns and extract the relation between them to introduce a formula using mathematical methods. Further, the resource discovery mechanism uses the formula to predict resources' load before assigning them new processes and thus it prevents resource overloading which happens frequently in computing environments. [ABSTRACT FROM AUTHOR]

A leader-follower facility problem is considered in this paper. The objective is to maximize the profit obtained by a chain (the leader) knowing that a competitor (the follower) will react by locating another single facility after the leader locates its own facility. A subpopulation-based evolutionary algorithm called TLUEGO was recently proposed to cope with this hard-to-solve global optimization problem. However, it requires high computational effort, even to manage small-size problems. In this work, three parallelizations of TLUEGO are proposed, a distributed memory programming algorithm, a shared memory programming algorithm, and a hybrid of the two previous algorithms, which not only allow us to obtain the solution faster, but also to solve larger instances. [ABSTRACT FROM AUTHOR]

Nowadays, we live in a Big Data world and many sectors of our economy are guided by data-driven decision processes. Big Data and Business Intelligence applications are facilitated by the MapReduce programming model, while, at infrastructural layer, cloud computing provides flexible and cost-effective solutions to provide on-demand large clusters. Capacity allocation in such systems, meant as the problem of providing computational power to support concurrent MapReduce applications in a cost-effective fashion, represents a challenge of paramount importance. In this paper we lay the foundation for a solution implementing admission control and capacity allocation for MapReduce jobs with a priori deadline guarantees. In particular, shared Hadoop 2.x clusters supporting batch and/or interactive jobs are targeted. We formulate a linear programming model able to minimize cloud resources costs and rejection penalties for the execution of jobs belonging to multiple classes with deadline guarantees. Scalability analyses demonstrated that the proposed method is able to determine the global optimal solution of the linear problem for systems including up to 10,000 classes in less than 1 s. [ABSTRACT FROM AUTHOR]

In recent years, deploying and running data-intensive workflows in cloud platform has become more and more popular in many areas. Unlike computation-intensive applications, a data-intensive workflow typically requires to deal with bulk data transferring between different resource sites, which means some traditional energy-efficiency optimization technologies are difficult to be enforced when running data-intensive workflows. In this paper, we first formulate the power model of a data-intensive workflow, which takes into account power consumption caused by data transferring. Based on this power model, we introduce a novel metric called Shortest Path in terms of Energy Consumption and design an energy-efficient heuristic scheduling algorithm, which is aiming at reducing the extra energy consumption caused by delays of bulk data transferring. Extensive experiments and performance evaluations show that the proposed scheduling algorithm can significantly reduce the overall energy consumption of running data-intensive workflows comparing with several existing algorithms. In addition, the proposed algorithm also exhibits better adaptiveness and robustness when a cloud system is facing intensive and unpredicted workloads. [ABSTRACT FROM AUTHOR]

The workflow scheduling problem has drawn a lot of attention in the research community. This paper presents a workflow scheduling algorithm, called granularity score scheduling (GSS), which is based on the granularity of the tasks in a given workflow. The main objectives of GSS are to minimize the makespan and maximize the average virtual machine utilization. The algorithm consists of three phases, namely B-level calculation, score adjustment and task ranking and scheduling. We simulate the proposed algorithm using various benchmark scientific workflow applications, i.e., Cybershake, Epigenomic, Inspiral and Montage. The simulation results are compared with two well-known existing workflow scheduling algorithms, namely heterogeneous earliest finish time and performance effective task scheduling, which are also applied in cloud computing environment. Based on the simulation results, the proposed algorithm remarkably demonstrates its performance in terms of makespan and average virtual machine utilization. [ABSTRACT FROM AUTHOR]

Current parallel systems composed of mixed multi/manycore systems and/with GPUs become more complex due to their heterogeneous nature. The programmability barrier inherent to parallel systems increases almost with each new architecture delivery. The development of libraries, languages, and tools that allow an easy and efficient use in this new scenario is mandatory. Among the proposals found to broach this problem, skeletal programming appeared as a natural alternative to easy the programmability of parallel systems in general, but also the GPU programming in particular. In this paper, we develop a programming skeleton for Dynamic Programming on MultiGPU systems. The skeleton, implemented in CUDA, allows the user to execute parallel codes for MultiGPU just by providing sequential C++ specifications of her problems. The performance and easy of use of this skeleton has been tested on several optimization problems. The experimental results obtained over a cluster of Nvidia Fermi prove the advantages of the approach. [ABSTRACT FROM AUTHOR]

This paper presents an overview of our experiments in integrating modern software engineering tools and techniques with the process of developing parallel applications for distributed memory architectures. The main goal was to determine the methods that have the potential of reducing the complexities associated with explicit parallelization. We experimented with template metaprogramming, aspect-oriented programming, program transformation engine, and a domain-specific language called Hi-PaL. The pros and cons of using each technique for explicit parallelization are presented in this paper. Our experiments demonstrate that through a combination of modern software engineering tools and techniques, the effort involved in explicit parallelization can be reduced by 90 % without any significant loss in performance. [ABSTRACT FROM AUTHOR]

Several protocols have been proposed to deal with the group key management problem in mobile ad hoc networks (MANETs). Most of these protocols organize the network into clusters to reduce the cost of key refresh or rekeying. Rekeying constitutes a challenging issue in group key management because it must be launched whenever the constitution of the group is altered following a leave or a join operation. However, cluster maintenance may also generate significative communication overhead. So, the clustering algorithm is an important factor in the performance of any key management solution. A clustering algorithm that ensures stable clusters in spite of mobility is very appreciable in mobile ad hoc networks. In fact, all the overhead due to the traffic generated by cluster adjustments and the related rekeying procedures will be saved. As far as we know, no existing clustering algorithm takes into account self-stabilization while relying on the mobility resilience of graph alliances. In this paper, we propose a fully distributed and self-stabilizing clustering algorithm for key management in MANETs where each cluster is an alliance. [ABSTRACT FROM AUTHOR]

Communication plays a critical role in the design and performance of multi-core systems-on-chip (SoCs). Networks-on-chip (NoCs) have been proposed as a promising solution to complex on-chip communication problems. As regular NoC topologies are infeasible to satisfy the performance demand for application-specific NoC, customized topology synthesis is therefore desirable. However, NoC topology synthesis problem is an NP-hard problem. In this paper, we propose a suboptimal genetic-algorithm based technique to synthesize application-specific NoC topology with system-level floorplan awareness. The method minimizes the power consumption and router resources while satisfying latency and bandwidth performance constraints. We have evaluated the proposed technique by running a number of representative benchmark applications and the results indicate that our method generates approximate optimal topologies effectively and efficiently for all benchmarks under consideration. [ABSTRACT FROM AUTHOR]

Synchronization/desynchronization and clustering are important techniques in multi-node computing systems, especially for sensor networks (SN) which is broadly considered to be a type of multi-node computing environment. However, most of the existing algorithms' clustering criteria are limited to the node location information and ignore the nature and characteristics of the nodes as well as the requirements of the applications. In this paper, an autonomic concurrent General Criteria-based Clustering (GCC) method is proposed for multi-node computing systems. The GCC method is based on the neuron oscillator pulse-coupling model and its clustering criteria can come from any node-related data or properties. The cluster member nodes share similar physical or logical properties and represent those relationships in the form of Logical Clusters (LCs). Due to the neuron dynamic system basis of the method, there is concurrency that exists both on the whole network and on each individual node. The simulation shows that the GCC method can generate diverse logical clusters and synchronization/desynchronization coexistence results with acceptable time and energy usage. [ABSTRACT FROM AUTHOR]

Programmers productivity has always been overlooked as compared to the performance optimizations in high performance computing (HPC) community. In many parallel programming languages like MPI/MPI-IO, the performance optimizations are provided as various function options to the programmers. In order to write an efficient code, they are required to know the exact usage of the optimization functions, hence programmer productivity is limited. In this paper, we present RFSA, a Reduced Function Set Abstraction based on an existing parallel programming interface (MPI-IO) for I/O. The purpose of RFSA is to hide the performance optimization functions from the application developer, and relieve the application developer from deciding on a specific function. The proposed set of functions rely on a selection algorithm to decide among the most common optimizations provided by MPI-IO. We implement a selection algorithm for I/O functions like read, write, etc., and also merge a set of functions for data types and file views. By running different parallel I/O benchmarks on both medium-scale clusters and NERSC supercomputers, we show an improved programmer productivity (35.7% on average). This approach incurs an overhead of 2-5% for one particular optimization, and shows performance improvement of 17% when a combination of different optimizations is required by an application. [ABSTRACT FROM AUTHOR]

With the rapid advance of computing technologies, it becomes more and more common to construct high-performance computing environments with heterogeneous commodity computers. Previous loop scheduling schemes were not designed for this kind of environments. Therefore, better loop scheduling schemes are needed to further increase the performance of the emerging heterogeneous PC cluster environments. In this paper, we propose a new heuristic for the performance-based approach to partition loop iterations according to the performance weighting of cluster/grid nodes. In particular, a new parameter is proposed to consider HPCC benchmark results as part of performance estimation. A heterogeneous cluster and grid were built to verify the proposed approach, and three kinds of application program were implemented for execution on cluster testbed. Experimental results show that the proposed approach performs better than the previous schemes on heterogeneous computing environments. [ABSTRACT FROM AUTHOR]

Predictions based on analytical performance models can be used on efficient scheduling policies in order to select adequate resources for an optimal execution in terms of throughput and response time. However, developing accurate analytical models of parallel applications is a hard issue. The TIA (Tools for Instrumenting and Analysis) modeling framework provides an easy to use modeling method for obtaining analytical models of MPI applications. This method is based on modeling selection techniques and, in particular, on Akaike's information criterion (AIC). In this paper, first the AIC-based performance model of the HPL benchmark is obtained using the TIA modeling framework. Then the use of this model for assessing the runtime estimation on different backfilling policies is analyzed in the GridSim simulator. The behavior of these simulations is compared with the equivalent simulations based on the theoretical model of the HPL provided by its developers. [ABSTRACT FROM AUTHOR]

llc is a C-based language where parallelism is expressed using compiler directives. In this paper, we present a new backend of an llc compiler that produces code for GPUs. We have also implemented a software architecture that eases the development of new backends. Our design represents an intermediate layer between a high-level parallel language and different hardware architectures. We evaluate our development by comparing the OpenMP and llc parallelizations of three different algorithms. In every case, the probable performance loss with respect to a direct CUDA implementation is clearly compensated by a significantly smaller development effort. [ABSTRACT FROM AUTHOR]

This paper presents a parameterized shared-memory scheme for parameterized metaheuristics. The use of a parameterized metaheuristic facilitates experimentation with different metaheuristics and hybridation/combinations to adapt them to the particular problem we are working with. Due to the large number of experiments necessary for the metaheuristic selection and tuning, parallelism should be used to reduce the execution time. To obtain parallel versions of the metaheuristics and to adapt them to the characteristics of the parallel system, a unified parameterized shared-memory scheme is developed. Given a particular computational system and fixed parameters for the sequential metaheuristic, the appropriate selection of parameters in the unified parallel scheme eases the development of parallel efficient metaheuristics. [ABSTRACT FROM AUTHOR]

Several parallel strategies for solving a centroid problem are presented. In the competitive location problem considered in this paper, the aim is to maximize the profit obtained by a chain (the leader) knowing that a competitor (the follower) will react by locating another single facility after the leader locates its own facility. A global optimization memetic algorithm called UEGO_cent.SASS was proposed to cope with this hard-to-solve optimization problem. Now, five parallel implementations of the optimization algorithm have been developed. The use of several processors, and hence more computational resources, allows us to solve bigger problems and to implement new methods which increase the robustness of the algorithm at finding the global optimum. A computational study comparing the new parallel methods in terms of efficiency and effectiveness has been carried out. [ABSTRACT FROM AUTHOR]

This paper describes several parallel algorithmic variations of the Neville elimination. This elimination solves a system of linear equations making zeros in a matrix column by adding to each row an adequate multiple of the preceding one. The parallel algorithms are run and compared on different multi- and many-core platforms using parallel programming techniques as MPI, OpenMP and CUDA. [ABSTRACT FROM AUTHOR]

Given a tree T=( V, E) of n nodes such that each node v is associated with a value-weight pair ( val, w), where value val is a real number and weight w is a non-negative integer, the density of T is defined as $\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}$. A subtree of T is a connected subgraph ( V′, E′) of T, where V′⊆ V and E′⊆ E. Given two integers w and w, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=( V′, E′) satisfying w≤∑ w≤ w. In this paper, we first present an O( w n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S⊂ V, we also present an O( w n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S. [ABSTRACT FROM AUTHOR]

Data races hamper parallel programming and threaten the reliability of future software. This paper proposes the data race prevention scheme View-Oriented Data race Prevention (VODAP), which can prevent data races in the View-Oriented Parallel Programming (VOPP) model. VOPP is a novel shared-memory data-centric parallel programming model, which uses views to bundle mutual exclusion with data access. We have implemented the data race prevention scheme with a memory protection mechanism. Experimental results show that the extra overhead of memory protection is trivial in our applications. The performance is evaluated and compared with modern programming models such as OpenMP and Cilk. [ABSTRACT FROM AUTHOR]

FT64 is the first 64-bit stream processor designed for scientific computing. It is critical to exploit optimizing streamization approaches for scientific applications on FT64 due to the inefficiency of direct streamization approach. In this paper, we propose a novel matrix-based streamization approach for improving locality and parallelism of scientific applications on FT64. First, a Data&Computation Matrix is built to abstract the relationship between loops and arrays of the original programs, and it is helpful for formulating the streamization problem. Second, three key techniques for optimizing streamization approach are proposed based on the transformations of the matrix, i.e., coarse-grained program transformations, fine-grained program transformations, and stream organization optimizations. Finally, we apply our approach to ten typical scientific application kernels on FT64. The experimental results show that the matrix-based streamization approach achieves an average speedup of 2.76 over the direct streamization approach, and performs equally to or better than the corresponding Fortran programs on Itanium 2 except CG. It is certain that the matrix-based streamization approach is a promising and practical solution to efficiently exploit the tremendous potential of FT64. [ABSTRACT FROM AUTHOR]

The special issue, Parallel and Distributed Processing with Applications, of "The Journal of Supercomputing" aims to provide a forum for computer scientists and engineers, applied mathematicians and researchers to present and exchange ideas, results, work in progress and experience of research in the area of parallel and distributed computing. The special issue is in conjunction with the 2003 International Symposium on Parallel and Distributed Processing and Applications (ISPA-03) held in Japan on July 2–4, 2003. There were very large amount paper submissions from 13 countries and regions.

Partial reconfiguration allows parts of the reconfigurable chip area to be configured without affecting the rest of the chip. This allows placement of tasks at run time on the reconfigurable chip. Area management is a very important issue which highly affect the utilization of the chip and hence the performance. This paper focuses on a major aspect of moving running tasks to free space for new incoming tasks (compaction). We study the effect of compacting running tasks to free more contiguous space on the system performance. First, we introduce a straightforward compaction strategy called Blind compaction. We use its performance as a reference to measure the performance of other compaction algorithms. Then we propose a two-dimensional compaction algorithm called one-corner compaction. This algorithm runs with respect to one chip corner. We further extend this algorithm to the four corners of the chip and introduce the four-corners compaction algorithm. Finally, we compare the performance of these algorithms with some existing compaction strategies: Brebner, G. and Diessel, O. (Proceedings of the 11th international workshop on field programmable gate arrays (FPL), pp. 182–191, ); Diesel, O. and ElGindy, H. (Proceedings of the 5th Australasian conference on parallel and real-time systems (PART), pp. 191–200, ); Diesel, O., et al. (IEE proceedings on computers and digital techniques, vol. 147, pp. 181–188, ). The simulation results show improvement in average task allocation time when using the four-corners compaction algorithm by 15% and in chip utilization by 16% over the Blind compaction. These results outperform the existing strategies. [ABSTRACT FROM AUTHOR]

Simultaneous transmission of multiple high quality video streams from a server to the clients is becoming an increasingly important class of traffic in a network of workstations or cluster environment. With a powerful symmetric multiprocessor (SMP) as the server and a high-speed network, such transmission is practicable from a hardware point of view. However, the actual construction of such a video data server system entails tackling a number of difficult problems related to the provision of strict quality of service (QoS) guarantees. Among others, the smoothing and scheduling of multiple video packet streams are two crucial issues. Smoothing is concerned with reducing the rate variability of video streams in view of the fact that video data are usually compressed in a variable bit rate fashion. Scheduling is important to guarantee the requested QoS levels while maximizing the utilization of the resources. Although much work on smoothing has been done, it is not clear which scheduling scheme is suitable for multiplexing smoothed video data to the network. In this paper we present an extensive performance study of the EDF and RM scheduling algorithms which are modified to provide QoS guarantees for smoothed video data. With a probabilistic definition of QoS, admission control conditions are incorporated into the two algorithms. Furthermore, a counter-based scheduling module is included as the core scheduling mechanism which adaptively adjusts the actual QoS levels assigned to requests. Our theoretical analysis of the two modified algorithms, called QEDF and QRM, shows that the QRM algorithm is more robust than the QEDF algorithm for different workload and utilization conditions. We also propose to use a new metric called meta-QoS to quantify the overall performance of a packet scheduler given a set of simultaneous requests. In our experiments based on an SMP-based Linux platform, we find that the QRM algorithm can sustain a rather stable level of meta-QoS even when the workload and utilization levels are increased. On the other hand, the QEDF algorithm, due to its conservative admission control policy, is found to be not suitable for a high level of utilization and a large number of requests. In view of the lower complexity of the QRM algorithm, it seems that the QRM approach is a more suitable candidate for packet scheduling in the client-server environment considered in our study. [ABSTRACT FROM AUTHOR]

Since user-level communication (ULC) architecture provides only primitive operations for application programmers, there have been several researches to build a portable and standard communication interface, such as sockets, on top of ULC architecture. Basically there are three different approaches to supporting the sockets interface over ULC architecture: LAN emulation, a user-level sockets, and a kernel-level sockets. The primary objective of this paper is to compare these approaches in terms of their design, implementation, and performance. We have developed and implemented a kernel-level sockets layer over ULC architecture, since there is currently no available implementation. We also present different design and implementation decisions on data receiving, data sending, connection management, etc. in the three approaches. Through the performance comparison, we show that LAN emulation approach exhibits the worst performance both in latency and bandwidth. Our experiments also show that a user-level sockets is useful for latency-sensitive applications and a kernel-level sockets is effective for applications which require high bandwidth and full compatibility with the legacy sockets interface. [ABSTRACT FROM AUTHOR]

This paper introduces an analytical method to approximate the fraction of jobs missing their deadlines in a soft real-time system when the earliest-deadline-first (EDF) scheduling policy is used. In the system, jobs either all have deadlines until the beginning of service (DBS) and are non-preemptive, or have deadlines until the end of service (DES) and are preemptive. In the former case, the system is represented by an M/M/m/EDF+G model, i.e., a multi-sever queue with Poisson arrival, exponential service, and generally distributed relative deadlines. In the latter case, it is represented by an M/M/1/EDF+G model, i.e., a single-server queue with the same specifications as before. EDF is known to be optimal in both of the above cases. The optimality property of EDF scheduling policy is used for the estimation of a key parameter, namely the loss rate when there are n jobs in the system. The estimation is possible by assuming an upper bound and a lower bound for this parameter and then linearly combining these two bounds together. The resulting Markov chains can then be easily solved numerically. Comparing numerical and simulation results, we find that the existing errors are relatively small. [ABSTRACT FROM AUTHOR]

Modern optimizing compilers apply a fixed sequence of optimizations, which we call a compilation sequence, to each program that they compile. These compilers let the user modify their behavior in a small number of specified ways, using command-line flags (e.g.,-O1,-O2,...). For five years, we have been working with compilers that automatically select an appropriate compilation sequence for each input program. These adaptive compilers discover a good compilation sequence tailored to the input program, the target machine, and a user-chosen objective function. We have shown, as have others, that program-specific sequences can produce better results than any single universal sequence [1, 7, 10, 21, 23] Our adaptive compiler looks for compilation sequences in a large and complex search space. Its typical compilation sequence includes 10 passes (with possible repeats) chosen from the 16 available—there are 1610 or [1,099,511,627,776] such sequences. To learn about the properties of such spaces, we have studied subspaces that consist of 10 passes drawn from a set of 5 (510 or 9,765,625 sequences). These 10-of-5 subspaces are small enough that we can analyze them thoroughly but large enough to reflect important properties of the full spaces.This paper reports, in detail, on our analysis of several of these subspaces and on the consequences of those observed properties for the design of search algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose an approach for the real-time performance analysis of distributed software with reliability constraints, called Athena. The approach is based on the real-time and reliability performance analysis of distributed program. In Athena, two important factors, imperfect nodes and the links reliability, are introduced. The algorithms proposed in Athena generates sub-graphs, counts the reliability of each sub-graph, calculates the transmission time for all the transmission paths of each data file, and computes response time of each data file with reliability constraint. In this way, the real-time performance of distributed software with reliability constrains can be evaluated. [ABSTRACT FROM AUTHOR]

Modifying the data distribution over the course of a program to adapt to variations in the data access patterns may leads to significant computational benefits in many scientific applications. Therefore, dynamic realignment of data is used to enhance algorithm performance in parallel programs on distributed memory machines. This paper presents a new method aims to the efficiency of block-cyclic data realignment of sparse matrix. The main idea of the proposed technique is first todevelop closed forms for generating theVector Index Set (VIS)of each source/destination processor. Based on the vector index set and the nonzero structure of sparse matrix, two efficient algorithms,vector2message (v2m) and message2vector (m2v)can be derived. The proposed technique usesv2mto extract nonzero elements from source compressed structures and packs them into messages in the source stage; and usesm2vto unpack each received messages and construct the destination matrix in the destination stage. A significant improvement of this approach is that a processor does not need to determine the complicated sending or receiving data sets for dynamic data redistribution. The indexing cost is reduced obviously. The second advantage of the present techniques is the achievement of optimal packing/unpacking stages consequent upon the informative VIS tables. Another contribution of our methods is the ability to handle sparse matrix redistribution under two disjoint processor grids in the source and destination phases. A theoretical model to analyze the performance of the proposed technique is also presented in this work. To evaluate the performance of our methods, we have implemented the present algorithms on an IBM SP2 parallel machine along with the Histogram method and a dense redistribution strategy. The experimental results show that our technique provides significant improvement for runtime data redistribution of sparse matrices in most test samples. [ABSTRACT FROM AUTHOR]

We describe and evaluate a novel approach for the automatic parallelization of programs that use pointer-based dynamic data structures, written in Java. The approach exploits parallelism among methods by creating an asynchronous thread of execution for each method invocation in a program. At compile time, methods are analyzed to determine the data they access, parameterized by their context. A description of these data accesses is transmitted to a run-time system during program execution. The run-time system utilizes this description to determine when a thread may execute, and to enforce dependences among threads. This run-time system is the main focus of this paper. More specifically, the paper details the representation of data accesses in a method and the framework used by the run-time system to detect and enforce dependences among threads. Experimental evaluation of an implementation of the run-time system on a four-processor Sun multiprocessor indicates that close to ideal speedup can be obtained for a number of benchmarks. This validates our approach. [ABSTRACT FROM AUTHOR]

Triggered by the ever increasing advancements in processor and networking technology, a cluster of PCs connected by a high-speed network has become a viable and cost-effective platform for the execution of computation intensive parallel multithreaded applications. However, there are two research issues to be tackled in the scheduling problem for PC cluster computing: (1) how to reduce the communication overhead of executing a multithreaded application on the cluster; (2) how to exploit the heterogeneity, which is unavoidable in an evolving PC cluster, for the application. In this paper, we propose to use a duplication based approach in scheduling tasks/threads to a heterogeneous cluster of PCs. In duplication based scheduling, critical tasks are redundantly scheduled to more than one machine, in order to reduce the number of inter-task communication operations. The start times of the succeeding tasks are also reduced. The task duplication process is guided given the system heterogeneity in that the critical tasks are scheduled or replicated in faster machines. The algorithm has been implemented in our experimental application parallelization system for generating multithreaded parallel code executable on a cluster of Pentium PCs. Our experiments, using three numerical applications and one protocol processing kernel (multithreading per request), have indicated that heterogeneity of PC cluster is indeed useful for optimizing the execution of parallel multithreaded programs. [ABSTRACT FROM AUTHOR]

Advances in mobile agent research have brought in a new method for network routing, ant routing. Recently, we have derived some preliminary results regarding the agent population growth property and the jumping behavior for an ant routing algorithm. The focus was on the expected number of agents in a node. In practice, the number of agents propagating on each network channel is also critical as the network channel bandwidth is limited. In this paper, we first propose two extended ant routing algorithms, and then provide an in-depth analysis on the population growth behavior of the propagating agents for these algorithms, both at nodes (hosts) and on edges (channels) of the network. [ABSTRACT FROM AUTHOR]

Achieving satisfactory performance results in heterogeneous computing environments, such as network of workstations (NOWs) made up of dissimilar processing elements, requires a careful choice of the workload to be assigned to each target machine. The use of approximate analytical models can help to understand which are the parameters that mostly affect performance. In this paper we will show how to study analytically the behavior of an existing parallel program, a Cholesky factorization code, running in a heterogeneous NOW under the PVM run-time system. Firstly, the Cholesky factorization algorithm is introduced, along with a description of the target computing environment. After an analysis of the load distribution, the construction of the analytical model of the application is described in thorough detail. Finally, the results predicted through the model are compared to the performance figures obtained by executing the program in the real computing environment. [ABSTRACT FROM AUTHOR]

Cloud computing is a kind of computing model on subscription basis. In cloud computing environment, there are a lot of cloud providers that present variety kind of services with different quality of services. Users have various kinds of applications that should be carried out on suitable cloud services. Consequently the users might encounter problems in choosing the best service. Hence selection of a method to compare services and to choose best service has been regarded as a challenge. In this paper we presented NSGA_SR approach that utilizes both objective and subjective assessments and models ranking problem as a multi objective optimization and then solves it with use of non-dominated sorting genetic algorithm. Numerical experiments, confirmed that the proposed approach outperforms available approaches in terms of flexibility and scalability with increasing number of users and services. Also it converges to optimization of goals and has good stability during the different generations. Also it includes no limitation regarding any additive new quality attribute, service or supplementary function. [ABSTRACT FROM AUTHOR]

Resource provisioning of appropriate resources to cloud workloads depends on the quality of service (QoS) requirements of cloud applications and is a challenging task. In cloud environment, heterogeneity, uncertainty and dispersion of resources encounter a problem of allocation of resources, which cannot be addressed with existing resource management frameworks. Resource scheduling, if done after efficient resource provisioning, will be more effective and the cloud resources would be scheduled as per the user requirements (QoS) on provisioned resources. Execution of cloud workloads should be as per QoS parameters to fully satisfy the cloud consumer. Therefore, based on QoS parameters, it is mandatory to predict and verify the resource provisioning before actual resource scheduling. In this paper, a resource provisioning and scheduling framework has been presented which caters to provisioned resource distribution and scheduling of resources. Cloud workloads have been re-clustered using k-means-based clustering algorithm after firstly clustering them through workload patterns to identify the QoS requirements of a workload, and then based on identified QoS requirements resources are provisioned before actual scheduling. Further, scheduling has been done based on different scheduling policies. Finally, the performance of the proposed framework has been evaluated in both real and simulated cloud environment and experimental results show that the framework provisions and schedules resource efficiently by considering energy consumption, execution cost and execution time as QoS parameters. [ABSTRACT FROM AUTHOR]

Transactional memory (TM) is a compelling alternative to simplify multithreaded programming that traditionally relies on error-prone lock-based synchronization for implementing cooperative tasks. Lazy-Lazy hardware TM is one of the most efficient schemes in today's hardware TM systems. Nonetheless, the commit protocol in these systems has severe impact on performance and energy. The SEQ in Scalable-TCC implementation (STCC-SEQ) is the most popular and efficient commit protocol to date. In this paper, we propose GCommit, a cost-effective hardware-based STCC-SEQ protocol. GCommit employs a G-Arbiter microarchitecture for achieving minimal-latency and high-efficient commits. We implement G-Arbiter with a standard 45 nm cell library. For a target 16-core CMP, a G-Arbiter just represents 0.07 % of the whole on-chip area, requiring marginal energy consumption. Full-system simulations of the target system with the STAMP benchmarks show that GCommit achieves average reductions of 15.7 and 13.7 % in execution time and energy, respectively, when compared with STCC-SEQ. [ABSTRACT FROM AUTHOR]

Routing and broadcasting are major parameters determining the performance of interconnection networks. In this paper, we propose a new Petersen-torus network $$\mathrm{NPT}(m, n)$$ by modifying the external edge definitions of the Petersen-torus network to improve its diameter and broadcasting times. We also show one-to-all broadcasting algorithms in $$\mathrm{NPT}(m, n)$$ using the single-link available and multiple-link available models. [ABSTRACT FROM AUTHOR]