Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “PROCESSOR”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,693 records · Page 94

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗

Investigating the Interplay between Energy Efficiency and Resilience in High Performance Computing

Energy efficiency and resilience are two crucial challenges for HPC systems to reach exascale. While energy efficiency and resilience issues have been extensively studied individually, little has been done to understand the interplay between energy efficiency and resilience for HPC systems. Decreasing the supply voltage associated with a given operating frequency for processors and other CMOS-based components can significantly reduce power consumption. However, this often raises system failure rates and consequently increases application execution time. In this work, we present an energy saving undervolting approach that leverages the mainstream resilience techniques to tolerate the increased failures caused by undervolting.

failures↗

LOGAN: High-Performance GPU-Based X-Drop Long-Read Alignment

Pairwise sequence alignment is one of the most computationally intensive kernels in genomic data analysis, accounting for more than 90% of the runtime for key bioinformatics applications. This method is particularly expensive for third-generation sequences due to the high computational cost of analyzing sequences of length between 1Kb and 1Mb. Given the quadratic overhead of exact pairwise algorithms for long alignments, the community primarily relies on approximate algorithms that search only for high-quality alignments and stop early when one is not found. In this work, we present the first GPU optimization of the popular X-drop alignment algorithm, that we named LOGAN. Results show that our high-performance multi-GPU implementation achieves up to 181.6 GCUPS and speed-ups up to 6.6× and 30.7× using 1 and 6 NVIDIA Tesla V100, respectively, over the state-of-the-art software running on two IBM Power9 processors using 168 CPU threads, with equivalent accuracy. We also demonstrate a 2.3× LOGAN speed-up versus ksw2, a state-of-art vectorized algorithm for sequence alignment implemented in minimap2, a long-read mapping software. Furthermore, to highlight the impact of our work on a real-world application, we couple LOGAN with a many-to-many long-read alignment software called BELLA, and demonstrate that our implementation improves the overall BELLA runtime by up to 10.6×. Finally, we adapt the Roofline model for LOGAN and demonstrate that our implementation is near optimal on the NVIDIA Tesla V100s.

97 MATHEMATICS AND COMPUTING↗

Communication-Avoiding and Memory-Constrained Sparse Matrix-Matrix Multiplication at Extreme Scale

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in various graph, scientific computing and machine learning algorithms. In this paper, we consider SpGEMMs performed on hundreds of thousands of processors generating trillions of nonzeros in the output matrix. Distributed SpGEMM at this extreme scale faces two key challenges: (1) high communication cost and (2) inadequate memory to generate the output. Furthermore, we address these challenges with an integrated communication-avoiding and memory-constrained SpGEMM algorithm that scales to 262,144 cores (more than 1 million hardware threads) and can multiply sparse matrices of any size as long as inputs and a fraction of output fit in the aggregated memory. As we go from 16,384 cores to 262,144 cores on a Cray XC40 supercomputer, the new SpGEMM algorithm runs 10x faster when multiplying large-scale protein-similarity matrices.

97 MATHEMATICS AND COMPUTING↗

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗

HPDR: High-Performance Portable Scientific Data Reduction Framework

The rapid growth in scientific data generation is outpacing advancements in computing systems necessary for efficient storage, transfer, and analysis, particularly in the context of exascale computing. With the deployment of first-generation exascale computing systems and next-generation experimental facilities, this gap is widening and necessitates effective data reduction techniques to manage enormous data volumes. Over the past decade, various data reduction methods, including lossless compression, error-controlled lossy compression, and data refactoring, have been developed to accelerate I/O in scientific workflows. Despite significant reductions in data volume, these methods introduce considerable computational overhead, which can become the new bottleneck in data processing. To mitigate this, GPU-accelerated data reduction algorithms have been introduced. However, challenges remain in their integration into exascale workflows, including limited portability across different GPU architectures, substantial memory transfer overhead, and reduced scalability on dense multi-GPU systems. To address these challenges, we propose HPDR, a high-performance and portable data reduction framework. HPDR is designed to enable the execution of state-of-the-art reduction algorithms across diverse processor architectures while reducing memory transfer overhead to 2.3 % of the original, resulting in up to 3.5× faster throughput compared to existing solutions. It also achieves up to 96% of the theoretical speedup in multi-GPU settings. In addition, evaluations on accelerating I/O operations at scale up to 1,024 nodes of the Frontier supercomputer demonstrate that HPDR can achieve up to 103 TB/s reduction throughput, providing up to 4× acceleration in parallel I/O performance compared to existing data reduction routines. This work highlights the potential of HPDR to significantly enhance data reduction efficiency in exascale computing environments.

Chen, Jieyang [University of Oregon]↗

Modeling Cooperative Threads to Project GPU Performance for Adaptive Parallelism

Most accelerators, such as graphics processing units (GPUs) and vector processors, are particularly suitable for accelerating massively parallel workloads. On the other hand, conventional workloads are developed for multi-core parallelism, which often scale to only a few dozen OpenMP threads. When hardware threads significantly outnumber the degree of parallelism in the outer loop, programmers are challenged with efficient hardware utilization. A common solution is to further exploit the parallelism hidden deep in the code structure. Such parallelism is less structured: parallel and sequential loops may be imperfectly nested within each other, neigh boring inner loops may exhibit different concurrency patterns (e.g. Reduction vs. Forall), yet have to be parallelized in the same parallel section. Many input-dependent transformations have to be explored. A programmer often employs a larger group of hardware threads to cooperatively walk through a smaller outer loop partition and adaptively exploit any encountered parallelism. This process is time-consuming and error-prone, yet the risk of gaining little or no performance remains high for such workloads. To reduce risk and guide implementation, we propose a technique to model workloads with limited parallelism that can automatically explore and evaluate transformations involving cooperative threads. Eventually, our framework projects the best achievable performance and the most promising transformations without implementing GPU code or using physical hardware. We envision our technique to be integrated into future compilers or optimization frameworks for autotuning.

Meng, Jiayuan↗

Snowflake: A Lightweight Portable Stencil DSL

Stencil computations are not well optimized by general-purpose production compilers and the increased use of multicore, manycore, and accelerator-based systems makes the optimization problem even more challenging. In this paper we present Snowflake, a Domain Specific Language (DSL) for stencils that uses a 'micro-compiler' approach, i.e., small, focused, domain-specific code generators. The approach is similar to that used in image processing stencils, but Snowflake handles the much more complex stencils that arise in scientific computing, including complex boundary conditions, higher-order operators (larger stencils), higher dimensions, variable coefficients, non-unit-stride iteration spaces, and multiple input or output meshes. Snowflake is embedded in the Python language, allowing it to interoperate with popular scientific tools like SciPy and iPython; it also takes advantage of built-in Python libraries for powerful dependence analysis as part of a just-in-time compiler. We demonstrate the power of the Snowflake language and the micro-compiler approach with a complex scientific benchmark, HPGMG, that exercises the generality of stencil support in Snowflake. By generating OpenMP comparable to, and OpenCL within a factor of 2x of hand-optimized HPGMG, Snowflake demonstrates that a micro-compiler can support diverse processor architectures and is performance-competitive whilst preserving a high-level Python implementation.

97 MATHEMATICS AND COMPUTING↗

A Study of Clustering Techniques and Hierarchical Matrix Formats for Kernel Ridge Regression

We present memory-efficient and scalable algorithms for kernel methods used in machine learning. Using hierarchical matrix approximations for the kernel matrix the memory requirements, the number of floating point operations, and the execution time are drastically reduced compared to standard dense linear algebra routines. We consider both the general H matrix hierarchical format as well as Hierarchically Semi-Separable (HSS) matrices. Furthermore, we investigate the impact of several preprocessing and clustering techniques on the hierarchical matrix compression. Effective clustering of the input leads to a ten-fold increase in efficiency of the compression. The algorithms are implemented using the STRUMPACK solver library. These results confirm that - with correct tuning of the hyperparameters - classification using kernel ridge regression with the compressed matrix does not lose prediction accuracy compared to the exact - not compressed - kernel matrix and that our approach can be extended to O(1M) datasets, for which computation with the full kernel matrix becomes prohibitively expensive. We present numerical experiments in a distributed memory environment up to 1,024 processors of the NERSC's Cori supercomputer using well-known datasets to the machine learning community that range from dimension 8 up to 784.

97 MATHEMATICS AND COMPUTING↗

Population Count on Intel® CPU, GPU, and FPGA

Population count is a primitive used in many applications. Commodity processors have dedicated instructions for achieving high-performance population count. Motivated by the productivity of high-level synthesis and the importance of population count, in this paper we investigated the OpenCL implementations of population count algorithms, and evaluated their performance and resource utilizations on an FPGA. Based on the results, we select the most efficient implementation. Then we derived a reduction pattern from a representative application of population count. We parallelized the reduction with atomic functions, and optimized it with vectorized memory accesses, tree reduction, and compute-unit duplication. We evaluated the performance of the reduction kernel on an Intel (R) Xeon (R) CPU and an Intel (R) IrisT Pro integrated GPU, and an FPGA card that features an Intel (R) Arria (R) 10 FPGA. When DRAM memory bandwidth is comparable on the three computing platforms, the FPGA can achieve the highest kernel performance for large workload. On the other hand, we described performance bottlenecks on the FPGA. To make FPGAs more competitive in raw performance compared to high-performant CPU and GPU platforms, it is important to increase external memory bandwidth, minimize data movement between a host and a device, and reduce OpenCL runtime overhead on an FPGA.

heterogeneous computing↗

An 85 nW IoT Node-Controlling SoC for MELs Power-Mode Management and Phantom Energy Reduction

This paper presents an ultra-low power (ULP) node-controlling system-on-chip (SoC) used for power-mode management and phantom energy reduction of miscellaneous electric loads (MELs). The SoC is powered from a single 2.5 V voltage supply enabled by the integrated power management unit (PMU) and can control up to 16 MELs due to the on-chip 16-channel correlator and the 32b RISC-V microprocessor. To further reduce the system power consumption, two clock domains have been adopted for the correlator and the processor separately. Fabricated in 65-nm CMOS, the measured minimum power consumption of the proposed SoC is only 85 nW at 0.45 V voltage supply and 1 kHz clock frequency. The measured maximum operating frequency can go up to 148 kHz with a 0.55 V supply. An application experiment successfully demonstrates that the SoC controls the power modes of MELs from wake-up to cut-off to save the average power and phantom energy.

power-mode management, phantom energy, phantom pow↗

Exascale Workload Characterization and Architecture Implications

We use a hybrid methodology based on binary instrumentation and performance counters to characterize a set of proxy applications (mini-apps and PETSc applications) representative of a broad range of scientific applications (and particularly DOE's future high performance computing workloads). From this empirical basis, we create statistical models that extrapolate application properties (instruction mix, memory size, and memory bandwidth) as a function of problem size. We validate them and project the first quantitative characterization of an exascale computing workload. Finally, the exascale workload is used to evaluate a radical new exascale architecture, stacked DRAM with processor under memory (PUM). Of the two projections, one shows major potential benefits in using PUM. However, the second, more conservative projection suggests that only a small number of exascale applications are likely to be memory-bandwidth limited, but even these are fundamentally memory-capacity limited.

Balaprakash, Prasanna↗

Prometheus: Scalable and Accurate Emulation of Task-Based Applications on Many-Core Systems.

Modeling the performance of non-deterministic parallel applications on future many-core systems requires the development of novel simulation and emulation techniques and tools. We present “Prometheus”, a fast, accurate and modular emulation framework for task-based applications. By raising the level of abstraction and focusing on runtime synchronization, Prometheus can accurately predict applications’ performance on very large many-core systems. We validate our emulation framework against two real platforms (AMD Interlagos and Intel MIC) and report error rates generally below 4%. We, then, evaluate Prometheus’ performance and scalability: our results show that Prometheus can emulate a task-based application on a system with 512K cores in 11.5 hours. We present two test cases that show how Prometheus can be used to study the performance and behavior of systems that present some of the characteristics expected from exascale supercomputer nodes, such as active power management and processors with a high number of cores but reduced cache per core.

exascale systems↗

Energy-Efficient and Secure S-Box circuit using Symmetric Pass Gate Adiabatic Logic

Differential Power Analysis (DPA) attack is considered to be a main threat while designing cryptographic processors. In cryptographic algorithms like DES and AES, S-Box is used to indeterminate the relationship between the keys and the cipher texts. However, S-box is prone to DPA attack due to its high power consumption. In this paper, we are implementing an energy-efficient 8-bit S-Box circuit using our proposed Symmetric Pass Gate Adiabatic Logic (SPGAL). SPGAL is energy-efficient as compared to the existing DPAresistant adiabatic and non-adiabatic logic families. SPGAL is energy-efficient due to reduction of non-adiabatic loss during the evaluate phase of the outputs. Further, the S-Box circuit implemented using SPGAL is resistant to DPA attacks. The results are verified through SPICE simulations in 180nm technology. SPICE simulations show that the SPGAL based S-Box circuit saves upto 92% and 67% of energy as compared to the conventional CMOS and Secured Quasi-Adiabatic Logic (SQAL) based S-Box circuit. From the simulation results, it is evident that the SPGAL based circuits are energy-efficient as compared to the existing DPAresistant adiabatic and non-adiabatic logic families. In nutshell, SPGAL based gates can be used to build secure hardware for lowpower portable electronic devices and Internet-of-Things (IoT) based electronic devices.

Kumar, Dinesh↗

A Digital Three Level Space Vector Modulator for High Frequency Vector Sequence Generation

This letter proposes a digital high-speed three-level space vector pulse width modulator (3L-SVPWM). A conventional 3L-SVPWM is typically computation-based, involving a sequential execution of sub-tasks on a digital signal processor (DSP) based controller. The resulting high computation time of 5.4 μs limits the implementation of additional control blocks for switching frequencies greater than 100 kHz. This is overcome by transforming sub-tasks into digital blocks with 1-0 decisions and simpler arithmetic operations. The sub-task blocks are executed concurrently on a programmable logic device (PLD). Hence, a fast 3L-SVPWM execution in 140 ns is achieved. The proposed digital 3L-SVPWM enables high switching frequency operation of wide bandgap (WBG) device-based 3 L inverters to generate high fundamental frequency waveforms. A finite state machine is an integral part of the proposed implementation with the ability to generate any vector sequence, maximizing the usage of redundant vector states in 3L-SVPWM. Here, the proposed digital 3L-SVPWM operation is demonstrated with a GaN-based 3 L active neutral point clamped (3L-ANPC) inverter. Experimental results are presented at 250 kHz switching frequency to generate vector sequences for center-aligned SVPWM (CA-SVPWM) and common mode voltage reduced SVPWM (CMVR-SVPWM). The results also showcase a high fundamental frequency generation capability of 10 kHz.

active neutral point clamped inverter↗

Bristol Ridge: A 28-nm $\times$ 86 Performance-Enhanced Microprocessor Through System Power Management

Power management techniques can be effective at extracting more performance and energy efficiency out of mature systems on chip (SoCs). For instance, the peak performance of microprocessors is often limited by worst case technology (Vmax), infrastructure (thermal/electrical), and microprocessor usage assumptions. Performance/watt of microprocessors also typically suffers from guard bands associated with the test and binning processes as well as worst case aging/lifetime degradation. Similarly, on multicore processors, shared voltage rails tend to limit the peak performance achievable in low thread count workloads. In this paper, we describe five power management techniques that maximize the per-part performance under the before-mentioned constraints. Using these techniques, we demonstrate a net performance increase of up to 15% depending on the application and TDP of the SoC, implemented on 'Bristol Ridge,' a 28-nm CMOS, dual-core x 86 accelerated processing unit.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

Dynamic Data-Driven SAR Image Reconstruction Using Multiple GPUs

According to the article, the reconstruction of nxn-pixel synthetic aperture radar (SAR) imagery using a backprojection algorithm incurs O(n 2 · m) cost, where m is the number of pulses. This paper presents dynamic data-driven multiresolution algorithms to speed up SAR backprojection on multiple graphics processing units (GPUs). A critical part of this spatially variant reconstruction process is load balancing, which circumvents asymmetric work assignment. Fine-tuned algorithms for GPUs are presented as a part of improving running time. Communication between processors is overlapped with GPU calculation to reduce communication time.

Engineering↗

On the Convergence of the Inexact Running Krasnosel'skii-Mann Method

This letter leverages a framework based on averaged operators to tackle the problem of tracking fixed points associated with maps that evolve over time. In particular, this letter considers the Krasnosel'skii-Mann (KM) method in a settings where: 1) the underlying map may change at each step of the algorithm, thus leading to a 'running' implementation of the KM method, and 2) an imperfect information of the map may be available. An imperfect knowledge of the maps can capture cases where processors feature a finite precision or quantization errors, or the case where (part of) the map is obtained from measurements. The analytical results are applicable to inexact running algorithms for solving optimization problems, whenever the algorithmic steps can be written in the form of (a composition of) averaged operators; examples are provided for inexact running gradient methods and the forward-backward splitting method. Convergence of the average fixed-point residual is investigated for the non-expansive case; linear convergence to a unique fixed-point trajectory is showen in the case of inexact running algorithms emerging from contractive operators.

97 MATHEMATICS AND COMPUTING↗