Search

Search algorithms are integral to numerous applications in computer science. With the prevalence of multi-core processors in contemporary computing devices, the parallelization of search algorithms has surfaced as a viable strategy for achieving significant performance enhancements. This paper offers a detailed examination of the performance improvements garnered through the parallelization of search procedures, with a particular emphasis on the Depth-First Search (DFS) algorithm as it pertains to pathway discovery in binary trees. The primary aim of this study was to contrast the performance of the conventional sequential DFS approach with a novel parallel strategy designed to exploit the computational capabilities of multi-core processors. By capitalizing on the resources available in modern desktop and laptop computers, it was intended to markedly diminish the processing time necessary for examining all possible pathways in both symmetrical and asymmetrical binary trees. A meticulous experimental evaluation was conducted using a varied assortment of binary trees, spanning perfectly balanced to highly skewed structures, to ensure a thorough assessment of the effectiveness of both strategies. The primary metric employed for performance evaluation was the total processing time, a crucial consideration for time-critical applications. The experimental results confirmed the superiority of the parallelized method over the conventional sequential DFS approach. The parallel technique demonstrated significantly lower processing times for pathway discovery in all binary tree scenarios tested. These performance enhancements were particularly noticeable in larger and more complex trees, underscoring the potential of parallelization for managing computationally demanding tasks. [ABSTRACT FROM AUTHOR]

The speed difference between high-performance CPUs and energy-efficient CPUs, which are found in asymmetric performance multicore processors, affects the current form of Amdahl’s law equation. This paper proposes two updates to that equation based on the performance evaluation results of a simple parallel pi program written with OpenCilk. Performance evaluation was done by measuring execution time and instructions per cycle (IPC). The performance evaluation of the parallel program executed on the Intel Core i5 1240P processor did not indicate decreased performance due to asymmetric performance. Instead, the program with efficient work-stealing advantages from OpenCilk performed well. In the case of using the execution time of the P-CPU as a reference to obtain speedup, the evaluation results in a sublinear speedup. Conversely, in the case of using the execution time of the E-CPU as a reference, the evaluation results in a superlinear speedup. This paper proposes two updates to Amdahl’s law equation based on these two evaluation results.

Amdahl's Law painted a bleak picture for large-scale computing. The implication was that parallelism was limited and therefore so was potential speedup. While Amdahl's contribution was seminal and important, it drove others vested in parallel processing to define more clearly why large-scale systems are critical to our future and how they fundamentally provide opportunities for speedup beyond Amdahl's predictions. In the early 2000s, much like Amdahl, we predicted dire consequences for large-scale systems due to power limits. While our early work was often dismissed, the implications were clear to some: power would ultimately limit performance. In this retrospective, we discuss how power-performance measurement and modeling at scale led to contributions that have driven server and supercomputer design for more than a decade. While the influence of these techniques is now indisputable, we discuss their connections, limits and additional research directions necessary to continue the performance gains our industry is accustomed to. [ABSTRACT FROM AUTHOR]

The conventional form of Amdahl's law states that speedup of calculations in a multiprocessor machine is limited by the definite constant value just due to the existence of some non-parallelizable part in any algorithm. This brief paper considers one more general reason, which prevents a growth of parallel performance: processes that implement distributed task cannot start simultaneously and hence every process adds some start-up time, also reducing by that the gain from a parallel processing. The simple formula, proposed here to extend Amdahl's law, leads to a less optimistic picture in comparison with classical results: for large amount of processor units the modified law does not approach to constant but vanishes. This is the result of competition between two factors: decreasing of calculation duty and increasing of start-up time when a number of parallel processes grows. The effect may be subdued by means of specific regularity in launching parallel processes. [ABSTRACT FROM AUTHOR]

Multi-/many-core, homogeneous or heterogeneous architectures, using the existing CMOS technology are inevitably approaching the limit of attainable power efficiency due to the fundamental limits in scaling. Negative Capacitance Field-Effect Transistor (NCFET) is rapidly emerging as an alternative technology that promises a multi-fold increase in the power efficiency of transistors, yet is compatible with the existing CMOS fabrication process. NCFET incorporates a ferroelectric (FE) layer within the transistor's gate stack, which exhibits a negative capacitance effect amplifying the internal voltage. NCFET has been in detail studied in both physics and devices/circuits communities where its superiority has been demonstrated in semiconductor measurements. However, the full promise of NCFET remains unmodeled and unquantified unless the research is further continued to the microarchitecture and system levels. This article, for the first time, explores system- and application-level benefits of NCFET-based multi-/many-core designs in terms of performance and power-efficiency compared to state-of-the-art FinFET-based designs. This exploration is done first through analytical modeling in which we extend Amdahl's law for NCFET multi-/many-cores, and then through quantitative modeling. The latter is achieved through RTL- and system-level simulations of NCFET-based multi-cores. The analytical modeling shows that a novel type of technology-based heterogeneity in which cores with the same microarchitecture but different FE thickness are combined is highly beneficial. Our exploration shows that this novel heterogeneity increases the power-efficiency by up to 3.5× over homogeneous systems and even achieves 8.3% better performance and 20% higher power-efficiency than conventional heterogeneity in the microarchitecture without having to cope with the complexity of managing different microarchitectures. [ABSTRACT FROM AUTHOR]

The aim of this paper is to investigate dense linear algebra algorithms on shared memory multicore architectures. The design and implementation of a parallel tiled WZ factorization algorithm which can fully exploit such architectures are presented. Three parallel implementations of the algorithm are studied. The first one relies only on exploiting multithreaded BLAS (basic linear algebra subprograms) operations. The second implementation, except for BLAS operations, employs the OpenMP standard to use the loop-level parallelism. The third implementation, except for BLAS operations, employs the OpenMP task directive with the depend clause. We report the computational performance and the speedup of the parallel tiled WZ factorization algorithm on shared memory multicore architectures for dense square diagonally dominant matrices. Then we compare our parallel implementations with the respective LU factorization from a vendor implemented LAPACK library. We also analyze the numerical accuracy. Two of our implementations can be achieved with near maximal theoretical speedup implied by Amdahl’s law.

Abstract With both knowing more and more details about how neurons and complex neural networks work and having serious demand for making performable huge artificial networks, more and more efforts are devoted to build both hardware and/or software simulators and supercomputers targeting artificial intelligence applications, demanding an exponentially increasing amount of computing capacity. However, the inherently parallel operation of the neural networks is mostly simulated deploying inherently sequential (or in the best case: sequential–parallel) computing elements. The paper shows that neural network simulators, (both software and hardware ones), akin to all other sequential–parallel computing systems, have computing performance limitation due to deploying clock-driven electronic circuits, the 70-year old computing paradigm and Amdahl’s Law about parallelized computing systems. The findings explain the limitations/saturation experienced in former studies.

A simple means of integrating the characteristics of networked processors under divisible loads into Amdahl's Law is presented. Amdahl's Law serves as an upper bound to these speedup results. Amdahl's Law with divisible load processing characteristics included serves as an upper bound to speedup for any model taking into consideration more detailed peculiarities of real systems such as the overhead of task creation, synchronization, resource contention and memory issues. [ABSTRACT FROM AUTHOR]

Models extending Amdahl's law have been developed to study the behavior of parallel programs energy consumption. In addition, it has been shown that energy consumption of those programs also relies on the layout of the resources on the chip, such as power supply. Other extensions over Amdahl's law have been conducted to study the behavior of parallel programs speedup for frequency variable processors. Previous models have focused on the use of Turbo Boost in the parallel regions of a program, without considering that Turbo Boost also affects the sequential regions. Hence, we present a model to analyze energy consumption of parallel programs executed on Intel multicore processors with Turbo Boost frequencies to cover this gap. The model is an extension to Amdahl's law, and it is validated with a double-precision matrix multiplication running on Intel multicore processors that enable Turbo Boost technology. [ABSTRACT FROM AUTHOR]

Copyright of Transactions of Beijing Institute of Technology is the property of Beijing University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Summary: Service availability is an important issue in optical networks. Much research attention has been drawn to the provisioning of reliable connections achieved by approaches such as routing and wavelength assignment and by protection and restoration mechanisms. In contrast, the research on upgrading networks to meet new or dynamic demands of service availability based on network upgrading process has been comparatively lacking. In this paper, we address this issue by upgrading service availability from the perspective of labor forces for network maintenance. Our approach is premised on the assumption that the time period for fixing an optical link can be reduced by using more network resources of labor forces. To model this concept, we conduct Amdahl's law, a well‐known theorem in parallel computing, to describe human teamwork. To show the effectiveness of this concept, we propose mixed integer linear programming aiming at either maximizing service availability under limited labor forces or minimizing labor forces for predetermined service availability. In addition, a heuristic algorithm for upgrading service availability is presented. Our experimental results show that our network upgrading process can improve service availability optimally with a fixed number of forces and the proposed heuristic algorithm can effectively save computation time. [ABSTRACT FROM AUTHOR]

Cache-partitioned architectures allow subsections of the shared last-level cache (LLC) to be exclusively reserved for some applications. This technique dramatically limits interactions between applications that are concurrently executing on a multicore machine. Consider n applications that execute concurrently, with the objective to minimize the makespan, defined as the maximum completion time of the n applications. Key scheduling questions are as follows: (i) which proportion of cache and (ii) how many processors should be given to each application? In this article, we provide answers to (i) and (ii) for Amdahl applications. Even though the problem is shown to be NP-complete, we give key elements to determine the subset of applications that should share the LLC (while remaining ones only use their smaller private cache). Building upon these results, we design efficient heuristics for Amdahl applications. Extensive simulations demonstrate the usefulness of co-scheduling when our efficient cache partitioning strategies are deployed. [ABSTRACT FROM AUTHOR]

The Discrete Event Systems Specification (DEVS) formalism has been widely disseminated in this magazine and elsewhere for its applicability to computational science and engineering. While research in parallel and distributed simulation has been active in the past several decades, the utility of many techniques for high-performance DEVS simulation has been limited. Recent research has shown that that a reconstruction of Amdahl's and Gustafson's laws for parallelizing sequential code can afford a better understanding of the underlying principles and their application to simulation of DEVS models. In this article, the author shows, in comparison to the ideal case, that a relatively simple protocol based on the DEVS abstract simulator is both generally applicable and able to achieve significant speedup in parallel distributed simulation. [ABSTRACT FROM PUBLISHER]

The problem of learning parallel computer performance is investigated in the context of multicore processors. Given a fixed workload, the effect of varying system configuration on performance is sought. Conventionally, the performance speedup due to a single resource enhancement is formulated using Amdahl's law. However, in case of multiple configurable resources the conventional formulation results in several disconnected speedup equations that cannot be combined together to determine the overall speedup. To solve this problem, we propose to (1) extend Amdahl's law to accommodate multiple configurable resources into the overall speedup equation, and (2) transform the speedup equation into a multivariable regression problem suitable for machine learning. Using experimental data from fifty-eight tests spanning two benchmarks (SPECCPU 2017 and PCMark 10) and four hardware platforms (Intel Xeon 8180M, AMD EPYC 7702P, Intel CoffeeLake 8700K, and AMD Ryzen 3900X), analytical models are developed and cross-validated. Findings indicate that in most cases, the models result in an average cross-validated accuracy higher than 95%, thereby validating the proposed extension of Amdahl's law. The proposed methodology enables rapid generation of multivariable analytical models to support future industrial development, optimization, and simulation needs. [ABSTRACT FROM AUTHOR]

As processor design has been transiting from homogeneous multicore processor to heterogeneous multicore processor, traditional Amdahl's law cannot meet the new challenges for asymmetric multicore system. In order to further investigate the impact factors related to the Overhead of Data Preparation (ODP) for Asymmetric multicore systems, we evaluate an asymmetric multicore system built with CPU-GPU by measuring the overheads of memory transfer, computing kernel, cache missing and synchronization. This paper demonstrates that decreasing the overhead of data preparation is a promising approach to improve the whole performance of heterogeneous system. [ABSTRACT FROM AUTHOR]

This work studies the influence of temperature on performance and scalability of 3D Chip Multiprocessors (CMP) from Amdahl's law perspective. We find that 3D CMP may reach its thermal limit before reaching its maximum power. We show that a high level of parallelism may lead to high peak temperatures even in small scale 3D CMPs, thus limiting 3D CMP scalability and calling for different, in-memory computing architectures. [ABSTRACT FROM AUTHOR]

We extend Amdahl’s law by considering the overhead of data preparation (ODP) for multicore systems, and apply it to three “traditional” multicore system scenarios (homogeneous symmetric multicore, asymmetric multicore, and dynamic multicore) and two new scenarios (heterogeneous CPU-GPU multicore and dynamic CPU-GPU multicore). It demonstrates that potential innovations in heterogeneous system architecture are indispensable to decrease ODP. [ABSTRACT FROM PUBLISHER]

By extending Amdahl's law, software developers can weigh the pros and cons of moving their applications to the cloud. [ABSTRACT FROM PUBLISHER]

To meet the needs of a diverse range of workloads, asymmetric multicore processors (AMPs) have been proposed, which feature cores of different microarchitecture or ISAs. However, given the diversity inherent in their design and application scenarios, several challenges need to be addressed to effectively architect AMPs and leverage their potential in optimizing both sequential and parallel performance. Several recent techniques address these challenges. In this article, we present a survey of architectural and system-level techniques proposed for designing and managing AMPs. By classifying the techniques on several key characteristics, we underscore their similarities and differences. We clarify the terminology used in this research field and identify challenges that are worthy of future investigation. We hope that more than just synthesizing the existing work on AMPs, the contribution of this survey will be to spark novel ideas for architecting future AMPs that can make a definite impact on the landscape of next-generation computing systems. [ABSTRACT FROM AUTHOR]