Search

Summary: Task‐based systems have become popular due to their ability to utilize the computational power of complex heterogeneous systems. A typical programming model used is the Sequential Task Flow (STF) model, which unfortunately only supports static task graphs. This can result in submission overhead and a static task graph that is not well‐suited for execution on heterogeneous systems. A common approach is to find a balance between the granularity needed for accelerator devices and the granularity required by CPU cores to achieve optimal performance. To address these issues, we have extended the STF model in the StarPU runtime system by introducing the concept of hierarchical tasks. This allows for a more dynamic task graph and, when combined with an automatic data manager, it is possible to adjust granularity at runtime to best match the targeted computing resource. That data manager makes it possible to switch between various data layout without programmer input and allows us to enforce the correctness of the DAG as hierarchical tasks alter it during runtime. Additionally, submission overhead is reduced by using large‐grain hierarchical tasks, as the submission process can now be done in parallel. We have shown that the hierarchical task model is correct and have conducted an early evaluation on shared memory heterogeneous systems using the Chameleon dense linear algebra library. [ABSTRACT FROM AUTHOR]

Summary: The high temperature of a processor chip reduces its lifetime by many years. Also, higher temperature increases the cooling cost as well. Hence, controlling the peak temperature and maintaining high performance are the two important objectives that are in general trade‐off with each other. The dynamic voltage and frequency scaling is often used to reduce the energy consumption by running the processor on lower voltage and frequencies. This eventually decreases the temperature. In this article, we propose a linear regression‐based online CPU governor to predict the future temperature with high accuracy and later adjust the frequencies of the processor such that the temperature does not increase the given threshold. Doing so controls the peak temperature as well as maintains high performance. Extensive experimentation revealed that the proposed governor decreases the peak temperature by 4%–5% without observing any performance penalty and also reduces the execution cost by 3%–10% compared to the state‐of‐the‐art. [ABSTRACT FROM AUTHOR]

Summary: Many sources such as historical archives, sensor readings, health systems, and machine records produce ever‐increasing but often unchanging data. These accumulating data create a need for faster processing. Bitmap index, which can take advantage of multi‐core and multiprocessor systems, is designed to process data that increase over time but do not change frequently. It has a well‐known advantage, especially in queries on data with low cardinality. However, bitmap index can handle high cardinality data efficiently because it can use its own compression algorithm. Bitmap index has many encoding schemes that affect query processing time. In this study, we developed an algorithm that improves query performance by using optimal encoding among bitmap encodings. With this optimization algorithm, we witnessed up to 40% performance increase in queries made with bitmap indexes created with different encodings. Furthermore, in comparison with a commonly used relational database, we found significant improvements in the number of query operations per second performed on optimized encoded bitmap indexes generated by the introduced algorithm. [ABSTRACT FROM AUTHOR]

Summary: The problem of designing efficient parallel algorithms to calculate the product of n numbers when the multipliers are large is a fundamental problem in many applications of computer science such as cryptography. In this work, we present a new parallel algorithm on exclusive read shared memory model. The performance of the introduced algorithm is measured based on three factors, namely, (1) the number of cores, (2) the size of the array, and (3) the size of the multiplier. The experimental study on a multi core system reveals that the introduced algorithm is faster than the best‐known optimal parallel algorithm. The improvement of the proposed algorithm in processing time compared to the best known parallel algorithm is 80% when the size of the array was 220 and the sizes of the multiplier were 1024, 2048, and 4096 bits. Moreover, our algorithm is a highly scalable parallel algorithm compared with the best‐known optimal parallel algorithm. [ABSTRACT FROM AUTHOR]

Summary: In this work, we pursue the idea of radically decoupling the floating point format used for arithmetic operations from the format used to store the data in memory. We complement this idea with a customized precision memory format derived by splitting the mantissa (significand) of standard IEEE formats into segments, such that values can be accessed faster if lower accuracy is acceptable. Combined with precision‐aware algorithms that dynamically adapt the data access accuracy to the numerical requirements, the customized precision memory format can render attractive runtime savings without impacting the memory footprint of the data or the accuracy of the final result. In an experimental analysis using the adaptive precision Jacobi method on diagonalizable test problems, we assess the benefits of the mantissa‐segmenting customized precision format on recent multi‐ and manycore architectures. [ABSTRACT FROM AUTHOR]

In this paper, we propose an energy-aware task management mechanism designed for the forward-in-time algorithms running on multicore central processing units (CPUs), where the multidimensional positive definite advection transport algorithm stencil-based algorithm is one of the representative examples. This mechanism is based on the dynamic voltage and frequency scaling technique and allows the reduction of energy consumption for an existing algorithm (or application) such that the predefined execution time is respected, without requiring any modifications in the algorithm itself. This paper also provides the formulation of a method for minimizing the energy consumption with time constraints, which is based on the adaptive scheduling with online modeling. Finally, using the autotuning technique, we provide the automation of the process for creation and determination of the best energy profile at runtime, even in the presence of additional CPU workloads. The experimental results on a 6-core computing platform show that the proposed mechanism provides the energy savings of up to 1.43x when compared to the default Linux scaling governor. Also, we confirm the effectiveness of the self-adaptive feature of the proposed mechanism, by showing its ability to maintain the requested execution time in spite of additional CPU workloads imposed by other applications. [ABSTRACT FROM AUTHOR]

In the past, the tenacious semiconductor problems of operating temperature and power consumption limited the performance growth for single-core microprocessors. Microprocessor vendors hence adopt the multicore chip organizations with parallel processing because the new technology promises faster and lower power needed. In a short time, this trend floods first the development of CPU, then also the other peripherals like GPU. Modern GPUs are very efficient in manipulating computer graphics, and their highly parallel structure makes them even more effective than general-purpose CPUs for a range of graphical complex algorithms. However, technology of multicore processor brought revolution and unavoidable collision to the programming personnel. Multicore processor has high performance; however, parallel processing brings not only the opportunity but also a challenge. The issue of efficiency and the way how programmer or compiler parallelizes the software explicitly are the keys that enhance the performance on multicore chip. In this paper, we propose a parallel programming approach using hybrid CUDA, OpenMP, and MPI programming. There would be two verificational experiments presented in the paper. In the first, we would verify the availability and correctness of the auto-parallel tools, and discuss the performance issues on CPU, GPU, and embedded system. In the second, we would verify how the hybrid programming could surely improve performance. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Symbolic computation has underpinned a number of key advances in Mathematics and Computer Science. Applications are typically large and potentially highly parallel, making them good candidates for parallel execution at a variety of scales from multi-core to high-performance computing systems. However, much existing work on parallel computing is based around numeric rather than symbolic computations. In particular, symbolic computing presents particular problems in terms of varying granularity and irregular task sizes that do not match conventional approaches to parallelisation. It also presents problems in terms of the structure of the algorithms and data. This paper describes a new implementation of the free open-source GAP computational algebra system that places parallelism at the heart of the design, dealing with the key scalability and cross-platform portability problems. We provide three system layers that deal with the three most important classes of hardware: individual shared memory multi-core nodes, mid-scale distributed clusters of (multi-core) nodes and full-blown high-performance computing systems, comprising large-scale tightly connected networks of multi-core nodes. This requires us to develop new cross-layer programming abstractions in the form of new domain-specific skeletons that allow us to seamlessly target different hardware levels. Our results show that, using our approach, we can achieve good scalability and speedups for two realistic exemplars, on high-performance systems comprising up to 32000 cores, as well as on ubiquitous multi-core systems and distributed clusters. The work reported here paves the way towards full-scale exploitation of symbolic computation by high-performance computing systems, and we demonstrate the potential with two major case studies. © 2016 The Authors. Concurrency and Computation: Practice and Experience Published by John Wiley & Sons Ltd. [ABSTRACT FROM AUTHOR]

The capabilities of multicore processors lead them to be widely adopted in systems at any scale, since their are able to provide more computing power at a lower consumption and dissipation cost. System designers are challenged to a deeper understanding of multicore functioning in order to fully exploit them while keeping the optimal balance between cores utilization and optimal throughput, response time and energy usage. Besides the advancement of general purpose CPUs, the same technological evolution leads to the rise of GPUs, dramatic evolution of graphical coprocessors, that are now affordable, efficient, dedicated computing units, capable of parallel computing and equipped with facilities that make them suited for supporting the main CPU of a system in running ordinary applications. The availability of commercial off-the-shelf (COTS) multicore computers, eventually equipped with one or more GPUs, makes them the basic building block of data centers devoted to cloud applications or scientific computing. The way to optimal exploitation of such a wide amount of computing power passes through the ability of matching the best scheduling of hardware resources with the software characteristics of the applications. This requires appropriate models and evaluation methods. Simulation and analytical techniques are essential tools to support the design and the management process of such architectures, but a sound characterization of the workloads is required. Typical workloads consist in multithreaded applications, with different characteristics, that dynamically span over the cores of multiple machines, connected by fast networks. In this paper we propose several parametric performance models for different configurations of multicore machines, with or without GPU support, running multiple class multithreaded applications, aiming to supply a detailed modeling help for complex data centers. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We present Palirria, a self-adapting work-stealing scheduling method for nested fork/join parallelism that can be used to estimate the number of utilizable workers and self-adapt accordingly. The estimation mechanism is optimized for accuracy, minimizing the requested resources without degrading performance. We implemented Palirria for both the Linux and Barrelfish operating systems and evaluated it on two platforms: a 48-core Non-Uniform Memory Access (NUMA) multiprocessor and a simulated 32-core system. Compared with state-of-the-art, we observed higher accuracy in estimating resource requirements. This leads to improved resource utilization and performance on par or better to executing with fixed resource allotments. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY This paper describes PENNANT, a mini-app that operates on general unstructured meshes (meshes with arbitrary polygons), and is designed for advanced architecture research. It contains mesh data structures and physics algorithms adapted from the Los Alamos National Laboratory radiation-hydrodynamics code FLAG and gives a sample of the typical memory access patterns of FLAG. The basic capabilities and optimization approaches of PENNANT are presented. Results are shown from sample performance experiments run on serial, multicore, and graphics processing unit implementations, giving an indication of how PENNANT can be a useful tool for studies of new architectures and programming models. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Gaussian elimination is a canonical linear algebra procedure for solving linear systems of equations. In the last few years, the algorithm has received a lot of attention in an attempt to improve its parallel performance. This article surveys recent developments in parallel implementations of Gaussian elimination for shared memory architecture. Five different flavors are investigated. Three of them are based on different strategies for pivoting: partial pivoting, incremental pivoting, and tournament pivoting. The fourth one replaces pivoting with the Partial Random Butterfly Transformation, and finally, an implementation without pivoting is used as a performance baseline. The technique of iterative refinement is applied to recover numerical accuracy when necessary. All parallel implementations are produced using dynamic, superscalar, runtime scheduling and tile matrix layout. Results on two multisocket multicore systems are presented. Performance and numerical accuracy is analyzed. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The latest trends in high performance computing systems show an increasing demand on the use of a large scale multicore system in an efficient way so that high compute-intensive applications can be executed reasonably well. However, the exploitation of the degree of parallelism available at each multicore component can be limited by the poor utilization of the memory hierarchy. Actually, the multicore architecture introduces some distinct features that are already observed in shared memory and distributed environments. One example is that subsets of cores can share different subsets of memory. In order to achieve high performance, it is imperative that a careful allocation scheme of an application is carried out on the available cores, based on a scheduling specification that considers not only processors characteristics but also memory contention. This paper proposes a multicore cluster representation that captures relevant performance characteristics in multicores systems such as the influence of memory hierarchy and contention on application performance. Improved performance was achieved by a branch-and-bound application applied to the partitioning sets problem that incorporated a memory aware load balancing strategy based on the proposed multicore cluster representation. An in-depth analysis on this application execution showed its applicability to modern systems. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

With the constantly increasing of number of cores in multicore processors, more emphasis should be paid to the on-chip interconnect. Performance and power consumption of an on-chip interconnect are directly affected by the network topology. Researchers have proposed various topologies to optimize these metrics. The efficiency can also be optimized by proper mapping of applications. Therefore in this paper, we propose a novel partially diagonal network-on-chip (PDNOC) design that takes advantage of both heterogeneous network topology and congestion-aware application mapping. We analyse the partially diagonal network in terms of interconnect structure, area usage, power consumption, routing algorithm and implementation complexity. The key insight that enables the PDNOC is that most communication patterns in real-world applications are hot-spot and bursty. We implement a full system simulation environment using SPLASH-2 benchmarks. Performance metrics of standard mesh, concentrated mesh, full diagonal mesh and four types of the proposed PDNOC are measured in terms of network latency, application execution time and energy delay product. Evaluation results show that on average, the proposed PDNOC designs provide up to 36% improvement in execution time over concentrated mesh, and 3.6× better energy delay product over fully connected diagonal network. PDNOC design with two adjacent PD networks is a better candidate for higher efficiency, while four PD networks provide better performance. Copyright © 2014 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY The future of designing optical networks focuses on the wavelength division multiplexing technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of optical fiber. However, when it is required to establish a set of demands, a problem comes up. This problem is known as routing and wavelength assignment problem. In this work, we have tackled the static routing and wavelength assignment problem by using multiobjective evolutionary computing. The algorithm applied is the differential evolution but modified with the Pareto tournaments concept for being adapted to the multiobjective context. By using OpenMP, an application programming interface that supports multiplatform shared memory multiprocessing programming, we have demonstrated that this algorithm is highly suitable to be parallelized. We have performed several experiments in multicore systems with two, four, and eight cores, obtaining 97.57% of mean efficiency. To ensure that our heuristic obtains relevant results, we have compared it with a parallel version of the standard fast nondominated sorting genetic algorithm. Finally, in order to show the goodness and effectiveness of the differential evolution with Pareto tournaments algorithm when dealing with this problem, we present diverse multiobjective comparisons with the nondominated sorting genetic algorithm and other approaches published in the literature. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Although modern computer hardware offers an increasing number of processing elements organized in nonuniform memory access (NUMA) architectures, prevailing middleware engines for executing business processes, workflows, and Web service compositions have not been optimized for properly exploiting the abundant processing resources of such machines. Amongst others, factors limiting performance are inefficient thread scheduling by the operating system, which can result in suboptimal use of system memory and CPU caches, and sequential code sections that cannot take advantage of multiple available cores. In this article, we study the performance of the JOpera process execution engine on recent multicore machines. We first evaluate its performance without any dedicated optimization for multicore hardware, showing that additional cores do not significantly improve performance, although the engine has a multithreaded design. Therefore, we apply optimizations on the basis of replication together with an improved, hardware-aware usage of the underlying resources such as NUMA nodes and CPU caches. Thanks to our optimizations, we achieve speedups from a factor of 2 up to a factor of 20 (depending on the target machine) when compared with a baseline execution 'as is'. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY A major design issue in embedded systems is reducing the power consumption because batteries have a limited energy budget. For this purpose, several techniques such as dynamic voltage and frequency scaling (DVFS) or task migration are being used. DVFS allows reducing power by selecting the optimal voltage supply, whereas task migration achieves this effect by balancing the workload among cores. This paper focuses on power-aware scheduling allowing task migration to reduce energy consumption in multicore embedded systems implementing DVFS capabilities. To address energy savings, the devised schedulers follow two main rules: migrations are allowed at specific points of time and only one task is allowed to migrate each time. Two algorithms have been proposed working under real-time constraints. The simpler algorithm, namely, single option migration (SOM) only checks just one target core before performing a migration. In contrast, the multiple option migration (MOM) searches the optimal target core. In general, the MOM algorithm achieves better energy savings than the SOM algorithm, although differences are wider for a reduced number of cores and frequency/voltage levels. Moreover, the MOM algorithm reduces energy consumption as much as 40% over the worst fit algorithm. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we present an efficient, easily parallelizable approach to solve planted motif problem (PMP). PMP is a well-studied problem in computational biology. It is useful in developing methods for finding transcription factor binding sites, classifying sequences, and building phylogenetic trees. Many approaches to solve PMP can be found in the literature. But the problem with those approaches is that they are difficult to parallelize as they have been designed for serial computers. In this paper, we propose a simple, easily parallelizable enumeration-based approach called BitBased. As with most other enumeration-based approaches that have been proposed to solve PMP, BitBased is also limited by memory for solving large-sized problems. To overcome this limitation, we propose various modifications, which not only reduce the memory requirement but also improve the performance of the approach. We have implemented our approach on multicore and GPU devices. We found that BitBased outperforms all the approaches proposed to solve PMP so far. BitBased is able to solve the (21,8) instance, which was not previously reported as solved in the literature. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY The subset-sum problem is a well-known NP-complete combinatorial problem that is solvable in pseudo-polynomial time, that is, time proportional to the number of input objects multiplied by the sum of their sizes. This product defines the size of the dynamic programming table used to solve the problem. We show how this problem can be parallelized on three contemporary architectures, that is, a 128-processor Cray Extreme Multithreading (XMT) massively multithreaded machine, a 16-processor IBM x3755 shared memory machine, and a 240-core NVIDIA FX 5800 graphics processing unit (GPU). We show that it is straightforward to parallelize this algorithm on the Cray XMT primarily because of the word-level locking that is available on this architecture. For the other two machines, we present an alternating word algorithm that can implement an efficient solution. Our results show that the GPU performs well for problems whose tables fit within the device memory. Because GPUs typically have memories in the order of 10GB, such architectures are best for small problem sizes that have tables of size approximately 1010. The IBM x3755 performs very well on medium-sized problems that fit within its 64-GB memory but has poor scalability as the number of processors increases and is unable to sustain performance as the problem size increases. This machine tends to saturate for problem sizes of 1011 bits. The Cray XMT shows very good scaling for large problems and demonstrates sustained performance as the problem size increases. However, this machine has poor scaling for small problem sizes; it performs best for problem sizes of 1012 bits or more. The results in this paper illustrate that the subset-sum problem can be parallelized well on all three architectures, albeit for different ranges of problem sizes. The performance of these three machines under varying problem sizes show the strengths and weaknesses of the three architectures. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, we consider the problem of scheduling streaming applications described by complex task graphs on a heterogeneous multicore platform, the IBM QS 22 platform, embedding two STI Cell Broadband Engine processor. We first derive a complete computation and communication model of the platform on the basis of comprehensive benchmarks. Then we use this model to express the problem of maximizing the throughput of a streaming application on this platform. Although the problem is proven NP-complete, we present an optimal solution based on mixed linear programming. We also propose simpler scheduling heuristics to compute mapping of the application task graph on the platform. We then come back to the platform and propose a scheduling software to deploy streaming applications on this platform. This allows us to thoroughly test our scheduling strategies on the real platform. We thus show that we are able to achieve a good speed-up either with the mixed linear programming solution or using involved scheduling heuristics. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We present a new scheme for evaluating the performance of multithreaded computers and demonstrate its application to the Cray MTA-2 and XMT supercomputers. Our scheme is based on the concept of clock cycles per element, \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}${\cal C}$\end{document}, plotted against both problem size and the number of processors. This scheme clearly shows if an implementation has achieved its asymptotic efficiency and is more general than (but includes) the commonly used speedup metric. It permits the discovery of any imperfections in both the software as well as the hardware, and is expected to permit a unified comparison of many different parallel architectures. Measurements on a number of well-known parallel algorithms, ranging from matrix multiply to quicksort, are presented for the MTA-2 and XMT and highlight some interesting differences between these machines. The performance of sequence alignment using dynamic programming is evaluated on the MTA-2, XMT, IBM x3755 and SGI Altix 350 and provides a useful comparison of the capabilities of the Cray machines with more conventional shared memory architectures. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

State-of-the-art dense linear algebra software, such as the LAPACK and ScaLAPACK libraries, suffers performance losses on multicore processors due to their inability to fully exploit thread-level parallelism. At the same time, the coarse–grain dataflow model gains popularity as a paradigm for programming multicore architectures. This work looks at implementing classic dense linear algebra workloads, the Cholesky factorization, the QR factorization and the LU factorization, using dynamic data-driven execution. Two emerging approaches to implementing coarse–grain dataflow are examined, the model of nested parallelism, represented by the Cilk framework, and the model of parallelism expressed through an arbitrary Direct Acyclic Graph, represented by the SMP Superscalar framework. Performance and coding effort are analyzed and compared against code manually parallelized at the thread level. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

With the proliferation of large multicore high-performance computing systems, application performance is often negatively affected. This paper provides benchmark results for a representative workload from the Department of Defense High-performance Computing Modernization Program. The tests were run on a Cray XT-3 and XT-4, which use dual- and quad-core AMD Opteron microprocessors. We use a combination of synthetic kernel and application benchmarks to examine the cache performance, MPI task placement strategies and compiler optimizations. Our benchmarks show performance behavior similar to that reported in other studies and sites. Dual- and quad-core tests show a run-time performance penalty compared with single-core runs on the same systems. We attribute this performance degradation to a combination of L1 to main memory contention and task placement within the application. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The creation of a contemporary artwork –The Scalable City—explores the possibilities and implications of new technologies in general and the Cell processor (CP) in particular. In general, new technologies provide new methods for describing and acting in the world. Creating new forms of art can be a means of understanding and furthering this process; however, this has not been the typical relationship between the leading edges of cultural and technological experiments in the 20 th century. The approaches taken to create The Scalable City provide an example of how these goals can correlate in an effective way, as its aim is the creation of a 3D interactive graphics application, highlighting the ongoing algorithmicization of the world at large. In its creation, computational bottlenecks have been encountered, which compromised its aesthetic and conceptual goals. The core component of this work is a world depicting transforming landscapes, networks of roads and emergent structures. Within the operation of the artwork, each is transformed by interactions of the viewer, algorithms and the initial data. The computational demands of some of these transformations exceed the capability of standard methods using a single host compute environment. Sheldon Brown and the members of his Experimental Game Lab at the Center for Research in Computing and the Arts at UCSD developed means of using CP compute servers to overcome these limitations. The authors detail their encounters with Cell processing, from initial efforts, discovery of the affordances and limitations of Cell processing, and its eventual application to the project. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Cell/B.E. is a heterogeneous multicore processor that was designed for the efficient execution of parallel and vectorizable applications with high computation and memory requirements. The transition to multicores introduces the challenge of providing tools that help programmers tune the code running on these architectures. Tracing tools, in particular, often help locate performance problems related to thread and process communication. A major impediment to implementing tracing on Cell is the absence of a common clock that can be accessed at low cost from all cores. The OS clock is costly to access from the auxiliary cores and the hardware timers cannot be simultaneously set on all the cores. In this paper, we describe an offline trace analysis algorithm that assigns wall-clock time to trace records based on their thread-local time stamps and event order. Our experiments on several Cell SDK workloads show that the indeterminism in assigning wall-clock time to events is low, on average 20–40 clock ticks (translating into 1.4–2.8 µs on the system used in our experiments). We also show how various practical problems, such as the imprecision of time measurement, can be overcome. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We discuss the application of Web 2.0 to support scientific research (e-Science) and related ‘e-more or less anything’ applications. Web 2.0 offers interesting technical approaches (protocols, message formats, and programming tools) to build core e-infrastructure (cyberinfrastructure) as well as many interesting services (Facebook, YouTube, Amazon S3/EC2, and Google maps) that can add value to e-infrastructure projects. We discuss why some of the original Grid goals of linking the world's computer systems may not be so relevant today and that interoperability is needed at the data and not always at the infrastructure level. Web 2.0 may also support Parallel Programming 2.0—a better parallel computing software environment motivated by the need to run commodity applications on multicore chips. A ‘Grid on the chip’ will be a common use of future chips with tens or hundreds of cores. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

As multicore systems continue to gain ground in the high-performance computing world, linear algebra algorithms have to be reformulated or new algorithms have to be developed in order to take advantage of the architectural features on these new processors. Fine-grain parallelism becomes a major requirement and introduces the necessity of loose synchronization in the parallel execution of an operation. This paper presents an algorithm for the QR factorization where the operations can be represented as a sequence of small tasks that operate on square blocks of data (referred to as ‘tiles’). These tasks can be dynamically scheduled for execution based on the dependencies among them and on the availability of computational resources. This may result in an out-of-order execution of the tasks that will completely hide the presence of intrinsically sequential tasks in the factorization. Performance comparisons are presented with the LAPACK algorithm for QR factorization where parallelism can be exploited only at the level of the BLAS operations and with vendor implementations. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Summary: All‐to‐all communication is a basic functionality of parallel communication libraries such as the Message Passing Interface (MPI). Typically, there are multiple different underlying algorithms, which are chosen according to message size. We propose a communication algorithm, which exploits the fact that modern supercomputers combine shared memory parallelism and distributed memory parallelism. The application example of our algorithm is FFTs with pencil decomposition. Furthermore, we propose an extension of the MPI standard in order to accommodate this and other algorithms in an efficient way. [ABSTRACT FROM AUTHOR]

Summary: Self‐adaptability is a highly preferred feature in HPC applications. A crucial building block of a self‐adaptable application is a data partitioning algorithm that must possess several essential qualities apart from low runtime and memory costs. On modern platforms composed of multicore CPU processors, data partitioning algorithms striving to solve the bi‐objective optimization problem for performance and energy (BOPPE) face a formidable challenge. They must take into account the new complexities inherent in these platforms such as severe resource contention and non‐uniform memory access (NUMA). Novel model‐based methods and data partitioning algorithms have been proposed that address the challenge. However, these methods take as input full functional performance and energy models (FPM and FEM), which have prohibitively high model construction costs. Therefore, they are not suitable for employment in self‐adaptable applications. In this paper, we present a self‐adaptable data partitioning algorithm called ADAPTALEPH, which solves BOPPE on homogeneous clusters of multicore CPUs. Unlike the state‐of‐the‐art solving BOPPE that take as inputs full FPM and FEM, it constructs partial FPM and FEM during its execution using all the available processors. It returns a locally Pareto‐optimal set of solutions, which are the heterogeneous workload distributions that achieve inter‐node optimization of data‐parallel applications for performance and energy. We experimentally study the efficiency of ADAPTALEPH for three data‐parallel applications, ie, matrix‐vector multiplication, matrix‐matrix multiplication, and fast Fourier transform, on a modern multicore CPU and simulations for homogeneous clusters of such CPUs. We demonstrate that the locally Pareto‐optimal front approaches the globally Pareto‐optimal front as the number of points in the partial discrete FPM and FEM functions are increased. The number of points in the partial FPM/FEM when the locally Pareto‐optimal front becomes the globally Pareto‐optimal front is considerably less than the number of points in the full FPM/FEM thereby suggesting development of methods that can leverage this finding to drastically reduce the model construction times. [ABSTRACT FROM AUTHOR]

Summary: Binding parallel tasks to cores according to a placement policy is one of the key aspects to achieve good performance in multicore machines because it can reduce on‐chip communication among parallel threads. Binding also prevents operating system from migrating threads, which improves data locality. However, there is no single mapping policy that works best among all different kinds of applications and platforms because each machine has a different topology and each application exhibits different communication pattern. Determining the best policy for a given application and machine requires extra programming effort. To relieve the programmer from that burden, we introduce BindMe, a thread binding library that assists programmer to bind threads to underlying hardware. BindMe incorporates state‐of‐the‐art mapping algorithms, which use communication pattern in an application to formulate an efficient task placement policy. We also introduce ChoiceMap, a communication aware mapping algorithm that respects mutual priorities of parallel tasks and performs a fair mapping by reducing communication volume among cores. We have tested BindMe and ChoiceMap with various applications from NAS parallel benchmark and Rodinia bechmark. Our results show that choosing a mapping policy that best suits the application behavior can increase its performance and no single policy gives the best performance across different applications. [ABSTRACT FROM AUTHOR]

We propose a heterogeneous on-chip interconnection aiming at high efficiency multicore processors. An ideal on-chip interconnection should have low latency, high throughput, low power consumption, and high scalability. However, these metrics are usually contradictory with each other. Besides, a design should focus on the requirements of real applications. We investigate the characteristics of several parallel applications. It is found that the distribution of traffic is similar as the power law. We also discovered hot spot traffic, as well as bursty traffic from applications. Meanwhile, the average injection rate of parallel applications is relatively low. The proposed network is based on a dual-net concentrated mesh, where 2 physical networks are implemented for processing different messages and improve throughput. A diagonal interconnection is used in the central part of the network for alleviating the traffic hot spot without significant hardware overhead. We evaluate the proposed design with synthetic traffic and real applications by using a simulator. Results indicate that, on average for 8 applications, the network latency of the proposed design has reduced by 32% compared with regular mesh. Concerning efficiency when executing applications, the average energy delay product of the proposed design is 52.7% and 29.7% better than mesh and concentrate mesh, respectively. [ABSTRACT FROM AUTHOR]