Many-Core Computing: Hardware and software

Cover
Contents
Preface
Part I Programming models, OS and applications
1 HPC with many core processors
1.1 MPI+OmpSs interoperability
1.2 The interposition library
1.3 Implementation of the MPI+OmpSs interoperability
1.4 Solving priority inversion
1.5 Putting it all together
1.6 Machine characteristics
1.7 Evaluation of NTChem
1.7.1 Application analysis
1.7.2 Parallelization approach
1.7.3 Performance analysis
1.8 Evaluation with Linpack
1.8.1 Application analysis
1.8.2 Parallelization approach
1.8.3 Performance analysis
1.9 Conclusions and future directions
Acknowledgments
References
2 From irregular heterogeneous software to reconfigurable hardware
2.1 Outline
2.2 Background
2.2.1 OpenCL's hierarchical programming model
2.2.2 Executing OpenCL kernels
2.2.3 Work-item synchronisation
2.3 The performance implications of mapping atomic operations to reconfigurable hardware
2.4 Shared virtual memory
2.4.1 Why SVM?
2.4.2 Implementing SVM for CPU/FPGA systems
2.4.3 Evaluation
2.5 Weakly consistent atomic operations
2.5.1 OpenCL's memory consistency model
2.5.1.1 Executions
2.5.1.2 Consistent executions
2.5.1.3 Data races
2.5.2 Consistency modes
2.5.2.1 The acquire and release consistency modes
2.5.2.2 The seq-cst consistency mode
2.5.2.3 The relaxed consistency mode
2.5.3 Memory scopes
2.5.4 Further reading
2.6 Mapping weakly consistent atomic operations to reconfigurable hardware
2.6.1 Scheduling constraints
2.6.2 Evaluation
2.7 Conclusion and future directions
Acknowledgements
References
3 Operating systems for many-core systems
3.1 Introduction
3.1.1 Many-core architectures
3.1.2 Many-core programming models
3.1.3 Operating system challenges
3.2 Kernel-state synchronization bottleneck
3.3 Non-uniform memory access
3.4 Core partitioning and management
3.4.1 Single OS approaches
3.4.2 Multiple OS approaches
3.5 Integration of heterogeneous computing resources
3.6 Reliability challenges
3.6.1 OS measures against transient faults
3.6.2 OS measures against permanent faults
3.7 Energy management
3.7.1 Hardware mechanisms
3.7.2 OS-level power management
3.7.3 Reducing the algorithmic complexity
3.8 Conclusions and future directions
References
4 Decoupling the programming model from resource management in throughput processors
4.1 Introduction
4.2 Background
4.3 Motivation
4.3.1 Performance variation and cliffs
4.3.2 Portability
4.3.3 Dynamic resource underutilization
4.3.4 Our goal
4.4 Zorua: our approach
4.4.1 Challenges in virtualization
4.4.2 Key ideas of our design
4.4.2.1 Leveraging software annotations of phase characteristics
4.4.2.2 Control with an adaptive runtime system
4.4.3 Overview of Zorua
4.5 Zorua: detailed mechanism
4.5.1 Key components in hardware
4.5.2 Detailed walkthrough
4.5.3 Benefits of our design
4.5.4 Oversubscription decisions
4.5.5 Virtualizing on-chip resources
4.5.5.1 Virtualizing registers and scratchpad memory
4.5.5.2 Virtualizing thread slots
4.5.6 Handling resource spills
4.5.7 Supporting phases and phase specifiers
4.5.8 Role of the compiler and programmer
4.5.9 Implications to the programming model and software optimization
4.5.9.1 Flexible programming models for GPUs and heterogeneous systems
4.5.9.2 Virtualization-aware compilation and auto-tuning
4.5.9.3 Reduced optimization space
4.6 Methodology
4.6.1 System modeling and configuration
4.6.2 Evaluated applications and metrics
4.7 Evaluation
4.7.1 Effect on performance variation and cliffs
4.7.2 Effect on performance
4.7.3 Effect on portability
4.7.4 A deeper look: benefits and overheads
4.8 Other applications
4.8.1 Resource sharing in multi-kernel or multi-programmed environments
4.8.2 Preemptive multitasking
4.8.3 Support for other parallel programming paradigms
4.8.4 Energy efficiency and scalability
4.8.5 Error tolerance and reliability
4.8.6 Support for system-level tasks on GPUs
4.8.7 Applicability to general resource management in accelerators
4.9 Related work
4.10 Conclusion and future directions
Acknowledgments
References
5 Tools and workloads for many-core computing
5.1 Single-chip multi/many-core systems
5.1.1 Tools
5.1.2 Workloads
5.2 Multi-chip multi/many-core systems
5.2.1 Tools
5.2.2 Workloads
5.3 Discussion
5.4 Conclusion and future directions
5.4.1 Parallelization of real-world applications
5.4.2 Domain-specific unification of workloads
5.4.3 Unification of simulation tools
5.4.4 Integration of tools to real products
References
6 Hardware and software performance in deep learning
6.1 Deep neural networks
6.2 DNN convolution
6.2.1 Parallelism and data locality
6.2.2 GEMM-based convolution algorithms
6.2.3 Fast convolution algorithms
6.3 Hardware acceleration and custom precision
6.3.1 Major constraints of embedded hardware CNN accelerators
6.3.2 Reduced precision CNNs
6.3.3 Bit slicing
6.3.4 Weight sharing and quantization in CNNs
6.3.5 Weight-shared-with-parallel accumulate shared MAC (PASM)
6.3.6 Reduced precision in software
6.4 Sparse data representations
6.4.1 L1-norm loss function
6.4.2 Network pruning
6.4.2.1 Fine pruning
6.4.2.2 Coarse pruning
6.4.2.3 Discussion
6.5 Program generation and optimization for DNNs
6.5.1 Domain-specific compilers
6.5.2 Selecting primitives
6.6 Conclusion and future directions
Acknowledgements
References
Part II Runtime management
7 Adaptive–reflective middleware for power and energy management in many-core heterogeneous systems
7.1 The adaptive–reflective middleware framework
7.2 The reflective framework
7.3 Implementation and tools
7.3.1 Offline simulator
7.4 Case studies
7.4.1 Energy-efficient task mapping on heterogeneous architectures
7.4.2 Design space exploration of novel HMPs
7.4.3 Extending the lifetime of mobile devices
7.5 Conclusion and future directions
Acknowledgments
References
8 Advances in power management of many-core processors
8.1 Parallel ultra-low power computing
8.1.1 Background
8.1.2 PULP platform
8.1.3 Compact model
8.1.4 Process and temperature compensation of ULP multi-cores
8.1.4.1 Compensation of process variation
8.1.5 Experimental results
8.2 HPC architectures and power management systems
8.2.1 Supercomputer architectures
8.2.2 Power management in HPC systems
8.2.2.1 Linux power management driver
8.2.3 Hardware power controller
8.2.4 The power capping problem in MPI applications
References
9 Runtime thermal management of many-core systems
9.1 Thermal management of many-core embedded systems
9.1.1 Uncertainty in workload estimation
9.1.2 Learning-based uncertainty characterization
9.1.2.1 Multinomial logistic regression model
9.1.2.2 Maximum likelihood estimation
9.1.2.3 Uncertainty interpretation
9.1.3 Overall design flow
9.1.4 Early evaluation of the approach
9.1.4.1 Impact of workload uncertainty: H. 264 case study
9.1.4.2 Thermal improvement considering workload uncertainty
9.2 Thermal management of 3D many-core systems
9.2.1 Recent advances on 3D thermal management
9.2.2 Preliminaries
9.2.2.1 Application model
9.2.2.2 Multiprocessor platform model
9.2.2.3 3D IC model
9.2.3 Thermal-aware mapping
9.2.3.1 Thermal profiling
9.2.3.2 Runtime
9.2.3.3 Application merging
9.2.3.4 Resource allocation
9.2.3.5 Throughput computation
9.2.3.6 Utilization minimization
9.2.4 Experimental results
9.2.4.1 Benchmark applications
9.2.4.2 Target 3D many-core system
9.2.4.3 Temperature simulation
9.2.4.4 Interconnect energy computation
9.2.4.5 Thermal profiling results
9.2.4.6 Benchmark application results
9.2.4.7 Case-study for real-life applications
9.3 Conclusions and future directions
References
10 Adaptive packet processing on CPU–GPU heterogeneous platforms
10.1 Background on GPU computing
10.1.1 GPU architecture
10.1.2 Performance considerations
10.1.3 CPU – GPU heterogeneous platforms
10.2 Packet processing on the GPU
10.2.1 Related work
10.2.2 Throughput vs latency dilemma
10.2.3 An adaptive approach
10.2.4 Offline building of the batch-size table
10.2.5 Runtime batch size selection
10.2.6 Switching between batch sizes
10.3 Persistent kernel
10.3.1 Persistent kernel challenges
10.3.2 Proposed software architecture
10.4 Case study
10.4.1 The problem of packet classification
10.4.2 The tuple space search (TSS) algorithm
10.4.3 GPU-based TSS algorithm
10.4.4 TSS persistent kernel
10.4.5 Experimental results
10.5 Conclusion and future directions
References
11 From power-efficient to power-driven computing
11.1 Computing is evolving
11.2 Power-driven computing
11.2.1 Real-power computing
11.2.1.1 Hard real-power computing
11.2.1.2 Soft real-power computing
11.2.2 Performance constraints in power-driven systems
11.3 Design-time considerations
11.3.1 Power supply models and budgeting
11.3.2 Power-proportional systems design
11.3.2.1 Computation tasks
11.3.2.2 Communication tasks
11.3.3 Power scheduling and optimisation
11.4 Run-time considerations
11.4.1 Adapting to power variations
11.4.2 Dynamic retention
11.5 A case study of power-driven computing
11.6 Existing research
11.7 Research challenges and opportunities
11.7.1 Power-proportional many-core systems
11.7.2 Design flow and automation
11.7.3 On-chip sensing and controls
11.7.4 Software and programming model
11.8 Conclusion and future directions
References
Part III System modelling, verification, and testing
12 Modelling many-core architectures
12.1 Introduction
12.2 Scale-out vs. scale-up
12.3 Modelling scale-out many-core
12.3.1 CPR model
12.3.2 α Model
12.4 Modelling scale-up many-core
12.4.1 PIE model
12.4.2 β Model
12.5 The interactions between scale-out and scale-up
12.5.1 Φ Model
12.5.2 Investigating the orthogonality assumption
12.6 Power efficiency model
12.6.1 Power model
12.6.2 Model calculation
12.7 Runtime management
12.7.1 MAX-P: performance-oriented scheduling
12.7.2 MAX-E: power efficiency-oriented scheduling
12.7.3 The overview of runtime management
12.8 Conclusion and future directions
Acknowledgements
References
13 Power modelling of multicore systems
13.1 CPU power consumption
13.2 CPU power management and energy-saving techniques
13.3 Approaches and applications
13.3.1 Power measurement
13.3.2 Top-down approaches
13.3.3 Circuit, gate, and register-transfer level approaches
13.3.4 Bottom-up approaches
13.4 Developing top-down power models
13.4.1 Overview of methodology
13.4.2 Data collection
13.4.2.1 Power and voltage measurements
13.4.2.2 PMC event collection
13.4.3 Multiple linear regression basics
13.4.4 Model stability
13.4.5 PMC event selection
13.4.6 Model formulation
13.4.7 Model validation
13.4.8 Thermal compensation
13.4.9 CPU voltage regulator
13.5 Accuracy of bottom-up power simulators
13.6 Hybrid techniques
13.7 Conclusion and future directions
References
14 Developing portable embedded software for multicore systems through formal abstraction and refinement
14.1 Introduction
14.2 Motivation
14.2.1 From identical formal abstraction to specific refinements
14.2.2 From platform-independent formal model to platform-specific implementations
14.3 RTM cross-layer architecture overview
14.4 Event-B
14.4.1 Structure and notation
14.4.1.1 Context structure
14.4.1.2 Machine structure
14.4.2 Refinement
14.4.3 Proof obligations
14.4.4 Rodin: event-B tool support
14.5 From identical formal abstraction to specific refinements
14.5.1 Abstraction
14.5.2 Learning-based RTM refinements
14.5.3 Static decision-based RTM refinements
14.6 Code generation and portability support
14.7 Validation
14.8 Conclusion and future directions
References
15 Self-testing of multicore processors
15.1 General-purpose multicore systems
15.1.1 Taxonomy of on-line fault detection methods
15.1.2 Non-self-test-based methods
15.1.3 Self-test-based methods
15.1.3.1 Hardware-based self-testing
15.1.3.2 Software-based self-testing
15.1.3.3 Hybrid self-testing methods (hardware/software)
15.2 Processors-based systems-on-chip testing flows and techniques
15.2.1 On-line testing of CPUs
15.2.1.1 SBST test library generation constraints
15.2.1.2 Execution management of the SBST test program
15.2.1.3 Comparison of SBST techniques for in-field test programs development
15.2.2 On-line testing of application-specific functional units
15.2.2.1 Floating-point unit
15.2.2.2 Test for FPU
15.2.2.3 Direct memory access
15.2.2.4 Error correction code
15.3 Conclusion and future directions
References
16 Advances in hardware reliability of reconfigurable many-core embedded systems
16.1 Background
16.1.1 Runtime reconfigurable processors
16.1.2 Single event upset
16.1.3 Fault model for soft errors
16.1.4 Concurrent error detection in FPGAs
16.1.5 Scrubbing of configuration memory
16.2 Reliability guarantee with adaptive modular redundancy
16.2.1 Architecture for dependable runtime reconfiguration
16.2.2 Overview of adaptive modular redundancy
16.2.3 Reliability of accelerated functions (AFs)
16.2.4 Reliability guarantee of accelerated functions
16.2.4.1 Maximum resident time
16.2.4.2 Acceleration variants selection
16.2.4.3 Non-uniform accelerator scrubbing
16.2.5 Reliability guarantee of applications
16.2.5.1 Effective critical bits of accelerators
16.2.5.2 Reliability of accelerated kernels
16.2.5.3 Effective critical bits of accelerated kernels and applications
16.2.5.4 Budgeting of effective critical bits
16.2.5.5 Budgeting for kernels
16.2.5.6 Budgeting for accelerated functions
16.2.6 Experimental evaluation
16.3 Conclusion and future directions
Acknowledgements
References
Part IV Architectures and systems
17 Manycore processor architectures
17.1 Introduction
17.2 Classification of manycore architectures
17.2.1 Homogeneous
17.2.2 Heterogeneous
17.2.3 GPU enhanced
17.2.4 Accelerators
17.2.5 Reconfigurable
17.3 Processor architecture
17.3.1 CPU architecture
17.3.1.1 Core pipeline
17.3.1.2 Branch prediction
17.3.1.3 Data parallelism
17.3.1.4 Multi-threading
17.3.2 GPU architecture
17.3.2.1 Unified shading architecture
17.3.2.2 Single instruction multiple thread (SIMT) execution model
17.3.3 DSP architecture
17.3.4 ASIC/accelerator architecture
17.3.5 Reconfigurable architecture
17.4 Integration
17.5 Conclusion and future directions
17.5.1 CPU
17.5.2 Graphics processing units
17.5.3 Accelerators
17.5.4 Field programmable gate array
17.5.5 Emerging architectures
References
18 Silicon photonics enabled rack-scale many-core systems
18.1 Introduction
18.2 Related work
18.3 RSON architecture
18.3.1 Architecture overview
18.3.2 ONoC design
18.3.3 Internode interface
18.3.4 Bidirectional and sharable optical transceiver
18.4 Communication flow and arbitration
18.4.1 Communication flow
18.4.2 Optical switch control scheme
18.4.3 Channel partition
18.4.4 ONoC control subsystem
18.5 Evaluations
18.5.1 Performance evaluation
18.5.2 Interconnection energy efficiency
18.5.3 Latency analysis
18.6 Conclusions and future directions
References
19 Cognitive I/O for 3D-integrated many-core system
19.1 Introduction
19.2 Cognitive I/O architecture for 3D memory-logic integration
19.2.1 System architecture
19.2.2 QoS-based I/O management problem formulation
19.3 I/O QoS model
19.3.1 Sparse representation theory
19.3.2 Input data dimension reduction by projection
19.3.3 I/O QoS optimization
19.3.4 I/O QoS cost function
19.4 Communication-QoS-based management
19.4.1 Cognitive I/O design
19.4.2 Simulation results
19.4.2.1 Experiment setup
19.4.2.2 Adaptive tuning by cognitive I/O
19.4.2.3 Adaptive I/O control by accelerated
19.5 Performance-QoS-based management
19.5.1 Dimension reduction
19.5.2 DRAM partition
19.5.3 Error tolerance
19.5.4 Feature preservation
19.5.5 Simulation results
19.6 Hybrid QoS-based management
19.6.1 Hybrid management via memory (DRAM) controller
19.6.2 Communication-QoS result
19.6.3 Performance-QoS result
19.7 Conclusion and future directions
References
20 Approximate computing across the hardware and software stacks
20.1 Introduction
20.2 Component-level approximations for adders and multipliers
20.2.1 Approximate adders
20.2.1.1 Low-power approximate adders
20.2.1.2 Low-latency approximate adders
20.2.2 Approximate multipliers
20.3 Probabilistic error analysis
20.3.1 Empirical vs. analytical methods
20.3.2 Accuracy metrics
20.3.3 Probabilistic analysis methodology
20.4 Accuracy configurability and adaptivity in approximate computing systems
20.4.1 Approximate accelerators with consolidated error correction
20.4.2 Adaptive datapaths
20.5 Multi-accelerator approximate computing architectures
20.5.1 Case study: an approximate accelerator architecture for High Efficiency Video Coding (HEVC)
20.6 Approximate memory systems and run-time management
20.6.1 Methodology for designing approximate memory systems
20.6.2 Case study: an approximation-aware multilevel cells cache architecture
20.7 A cross-layer methodology for designing approximate systems and the associated challenges
20.8 Conclusion
References
21 Many-core systems for big-data computing
21.1 Workload characteristics
21.2 Many-core architectures for big data
21.2.1 The need for many-core
21.2.2 Brawny vs wimpy cores
21.2.3 Scale-out processors
21.2.4 Barriers to implementation
21.3 The memory system
21.3.1 Caching and prefetching
21.3.2 Near-data processing
21.3.3 Non-volatile memories
21.3.4 Memory coherence
21.3.5 On-chip networks
21.4 Programming models
21.5 Case studies
21.5.1 Xeon Phi
21.5.2 Tilera
21.5.3 Piranha
21.5.4 Niagara
21.5.5 Adapteva
21.5.6 TOP500 and GREEN500
21.6 Other approaches to high-performance big data
21.6.1 Field-programmable gate arrays
21.6.2 Vector processing
21.6.3 Accelerators
21.6.4 Graphics processing units
21.7 Conclusion and future directions
21.7.1 Programming models
21.7.2 Reducing manual effort
21.7.3 Suitable architectures and microarchitectures
21.7.4 Memory-system advancements
21.7.5 Replacing commodity hardware
21.7.6 Latency
21.7.7 Workload heterogeneity
References
22 Biologically-inspired massively-parallel computing
22.1 In the beginning…
22.2 Where are we now?
22.3 So what is the problem?
Microchip technology
Computer architecture
Deep networks
22.4 Biology got there first
Observations of biological systems
22.5 Bioinspired computer architecture
22.6 SpiNNaker – a spiking neural network architecture
22.6.1 SpiNNaker chip
22.6.2 SpiNNaker Router
22.6.3 SpiNNaker board
22.6.4 SpiNNaker machines
22.7 SpiNNaker applications
22.7.1 Biological neural networks
22.7.2 Artificial neural networks
22.7.3 Other application domains
22.8 Conclusion and future directions
Acknowledgements
References
Index