Transcript P-080618 Kernel Design Methodology

Weekly Group Meeting
on 18-06-2008
Project: Software Defined Radio Development using Network-On-Chip
based Rapid Prototyping Platform
By
Assad Saleem
Agenda
•
•
•
•
Kernel Design Methodology
NoC @ KTH
REXAPP architecture and Kernels
NOC design methodology
2
Kernel Design Methodology
•
•
•
•
•
Kernel Identification
Kernel Definition (Kernel inputs and outputs, operation/s on inputs)
Kernel Design (Kernel Hardware Architecture)
Kernel Implementation
Kernel Verification
3
Kernel Identification
4
Kernels for TDM (GSM) Tx/Rx
baseband Processing
• Modulation
• Burst forming &
Multiplexing
• Encryption
• Bit interleaving
• Channel Coding
• Speech Coding
• Demodulation
• De-multiplexing
•
•
•
•
Decryption
Bit De-interleaving
Channel Decoding
Speech Decoding
5
Kernels for CDMA Tx/Rx baseband
Processing
• Multiplexer
• Mapper
• Block interleaver
• Viterbi Encoder
• Correlator
• De-multiplexer
• Symbol Extraction,
Demapping
• De-interleaver
• Viterbi Decoder
• CRC Detector
6
Kernels for OFDMA Tx/Rx baseband
Processing
• Append Cyclic Prefix
• IFFT
• Sub-channelization &
Pilot Insertion
•
•
•
•
Symbol Mapping
Interleaving
FEC Coding
Randomization
• Remove Cyclic Prefix
• FFT
• De-subchannelization
& Pilot Extraction
• Channel Estimation,
Equalization and CFO
Correction
• Symbol De-mapping
• De-interleaving
• FEC Coding
• De-randomization
7
Common Kernels
• Multiplexer
• Symbol Mapping
• Interleaver
• De-multiplexer
• Symbol De-mapping
• De-interleaver
8
NoC @ KTH
• Project and objectives
– Network On Chip Architectures: NOCARC project is a threeyear research effort of 11 person between VTT Electronics, Oulu and
Royal Institute of Technology, Stockholm. The project has been funded
also by TEKES, VINNOVA, Nokia and Ericsson [1].
– The main challenge has been to study how to exploit efficiently the
one billion transistors silicon capacity available within next five years.
The main focus has been in the architectures, e.g. coarse-grain parallelism
and clustering, and in design methods, e.g. separation of infrastructure and
application development and supporting reuse [1].
9
NoC @ KTH
• Two architecture approaches
– Nostrum: an application specific NOC platform.
– Eclipse: a general purpose NOC platform
10
NoC @ KTH
• Nostrum: an application specific NOC platform.
A Nostrum chip is a matrix of resource slots containing integrated embedded
systems connected to each other via a two-dimensional mesh network using
deflection routing with congestion detection. The resources are heterogeneous
and their computing and storage capacity is designed according to applicationdomain characteristics. The Nostrum design methodology is a combination of
platform based design and distributed system design. It emphasizes the reuse
and the separation of infrastructure and application functionality [1].
Figure 1. The high-level architecture
of Nostrum. (P=processor
core, D=DSP core, C=cache memory
block, M=embedded
memory, L=dedicated logic block,
re=reconfigurable logic block,
rni=resource network interface, and
S=switch.) [1]
11
NoC @ KTH
• Eclipse: a general purpose NOC platform
An Eclipse chip consists of a set of super-pipelined multithreaded processors
attached to separate instruction memory modules, interleaved data memory
modules connected to each other via a double acyclic two dimensional sparse
mesh network with output-buffered greedy routing with two intermediate
targets. The design methodology for Eclipse is a variant of computing engine
based design and happens completely via software. The functionality is
described as a set of sequential and parallel application programs
communicating externally and internally via a single step accessible
synchronous shared memory [1].
Figure 2. The high-level architecture of
Eclipse. (P=processor,
I=instruction memory module, I/O=I/O
device, M=data memory
module, S=switch) [1].
12
NoC @ KTH
• Results:
– The main results have been Nostrum and Eclipse
architectures and related design methodologies that are
covering widely the NOC design space. The NOC
concept is a promising approach for extensive reuse and
management of complex communication patterns of
future systems [1].
– The NOCARC project has produced more than 30
scientific publications. The NOCARC project home
page at http://www.imit.kth.se/info/FOFU/NOC/
describes the project and researchers briefly and gives
the complete list of publications [1].
13
REXAPP architecture and Kernels [3]
Control Data
NOC
Switch
ScratchPad
Memory
Controller
RISC Processor
External
Memory
Interface
RF
Front End
Interface
Memory Data
NOC Switch
Inter-chip NOC
Replicator
Kernel
Figure-9(a): Conceptual view of a NOC tile
14
REXAPP architecture and Kernels [3]
External Memory
DDR2/Flash
PHY
PHY
PHY
RF Front End
A NOCtile
MAC
APPL.
REXAPP
System Controller
Figure 9(b): An example REXAPP System
15
A NOC Design Methodology
16
Design Flow Space [2]
profiling
simulation
synthesis
emulation
System exists
monitoring
workload
analysis
design
cosimulation
prototyping
complexity
analysis
mappability
estimation
capacity
estimation
mathematical
analyses
performance
modelling
analysis
System
does
not exist
estimation
performance
simulation
benchmarking
Resource development
17
Extremely short introduction to
existing design flows [2]
– Algorithm on Chip (AoC)
• ASIC design flow
• FPGA design flow
– System on Chip (SoC)
• Codesign flow
• IP based design flow
• Platform based design flow (Resources on Chip,
RoC)
– Configuration design flow
– Software design flow
18
AoC Design Flow [2]
Algorithms
exists
profiling
simulation
synthesis
emulation
Chip
exists
HW design
Algorithm
design
changes into
functionality
complexity
analysis
feasibility
studies
mathematical
analyses
System
does
not exist
modelling
Resource development
19
CoDesign Flow [2]
profiling
simulation
synthesis
emulation
System exists
monitoring
workload
analysis
cosimulation
prototyping
SW/HW
partitioning
mappability
estimation
mathematical
analyses
capacity
estimation
modelling
System
does
not exist
Resource development
20
IP Based Design [2]
emulation
System exists
monitoring
workload
analysis
cosimulation
prototyping
mappability
estimation
mathematical
analyses
System
does
not exist
modelling
capacity
estimation
IP block
integration
estimation
Architectur
e
template
Resource development
21
Software Design [2]
System
exists
monitoring
prototyping
SW design
performance
analysis
modelling
System
does
not exist
estimation
performance
simulation
Computer design
Resource development
RTOS
services
benchmarking
Computer
exists
22
Capacity of Network on Chip [2]
10 computers
Average SoC design  1 million gates
1 billion transistors  250 million gates
1 NoC > 200 SoCs
1 GHz clock with RISC computer 
1000 MIPS performance
1 NOC capacity  100-10000 GIPS
Applicability of capacity is limited by
communication
10 computers
23
“Applications” for NOC [2]
•
•
•
•
•
•
•
Multistandard terminal
Next generation base station
Simulation of human brain
Virtual reality creation
Telepresence
Holodeck (Star Trek)
Purpose of Life (Hitch Hikers Guide to
Galaxy)
• Simulation of universe
• Commercial operating system :-)
Piece of cake
Realistic
applications
Maybe not
even for NOC
Real
challenges for
every
archtitecture
24
Application characteristics [2]
NOC capacity
will be shared by
several
simultaneous
applications
Presentation
Search
Analysis
Communication
NOC must be
adaptable to
different workload
patterns
Streambased
processing
Different applications
have very different
requirement profile
tn
Computation
Storage
Communication
Parallel
processing
tn+
p
Real-time
processing
25
Network on Chip alternatives [2]
NOC = Network of computation and
storage resources
NOC parameters:
Number of resources
Types of resources
GPU
DSP
Memory
Configurable HW
Coprocessors
Any combination
Communication capability
26
Network on Chip alternatives [2]
Regions are used to encapsulate
application requirements
Parallel high-performance datapaths
Data compression, encryption,
decompression, decryption
OFDM bit-stream processing
WCDMA bit-stream processing
27
Network on Chip alternatives [2]
Memory
management
DATABASE
NOC
Memory area
Application
s
28
Network on Chip alternatives [2]
Parallel
processing
engine
IO
29
NOC design challenges [2]
Physical limits -> Architecture basics ->
GALS -> Communication principles
Application requirements -> Region concepts ->
Heterogenuous resources types -> Multilanguage
and method design flows
Overall complexity -> Architecture reuse ->
Platform type of design flow
Overall complexity -> Basic control
principles -> System services
NoC
SoC
Manufacturability problems -> Structured approach
30
Figure of Merit for NOC based
systems [2]
Computation
Storage
Communication
Scalability
Efficiency
Utilisation
Energy
Capacityconsumption
Functionality
Fault tolerance
Result quality (accuracy)
Responsiveness
Performance
Structural
Functional
Control
Complexity
Materials
Licencing
Production
System
Quality
Variability
Implementation
Cost
Development
Flexibility
Applicability
Configurability
Programmability
Modifiability
Coupling
Cohesion
Modularity
Volume
Effort
Time
Risk
Lifetime
Manufacturability
Usability
31
Basic requirements for
NOC design methodology [2]
•
•
•
Reuse
– of intellectual property blocks
• best performance/energy ratio
• best mapping to application characteristics
Reuse
– of hardware (and architecture)
• best complexity/cost and performance/cost ratio
• only way to even dream of achieving time-to-profit requirements
Reuse
– of design methods and tools
• only way to deal with heterogenuous application set
32
NOC Design Methodology [2]
Cores
Communication
structure
Generic backbone
Memories
Accelerators
Definition of
NOC platform
Optimised Virtual Components
“Application area specific IPR”
Processors
and hardware
Algorithms
Product area specific platform
Code and
configuration
Applications
Instantiation
of NoC
platform
“Product specific IPR”
Features
Optimised Intellectual Property
NoC system
33
Structural layers of NOC [2]
Product
System control, product behaviour
Configuration
Network management, allocation, operation modes
Applications
Resource management,diagnostics, applications
Functions
Executables
Hardware units
Resources
Regions
Communication
Execution control, functions
RTOS, code, HW configurations
Processors, memorires, configurable HW, logic
Resource types, buses, IO
Region types, switches, network interfaces
Channels and protocols
34
Logical layers of NOC [2]
• Backbone
– Communication resources
– Basic set of system services
– Architecture design methods and tools
• Platform
– Computation and storage resources
– System services
– Application design methods and tools
Product
Configuration
Applications
Functions
Executables
Hardware units
Resources
Regions
Communication
• System
– Functionality of computation(code, configuration)
– Control (OS, NetOS)
– Validation and verification support
35
Development of NOC based systems [2]
High-perforrmance
communication systems
High-capacity
communication
systems
Baseband platform
Database platform
Personal
assistant
Data
collection
systems
BACKBONE
Entertainmen
t devices
Multimedia platform
PLATFORMS
SYSTEMS
Virtual reality games
36
Using Design Space for NOC [2]
Communication
channels
Non-configurable
hardware
Application
mapping
Backbone
Architecture
design
NOC System
Product differentiation
Platform
System Services
Operation principles
Product area specialisation
System
does
not exist
Resource development
37
System Services [2]
• Purpose to hide implementation
details from application developer
Applications
– Execution services
• Communication, resource allocation
and conversion services
System Services
– Control services
– Development support services
• Language interfacing, compilers,
libraries, optimisations, debugging,
testing, validation, etc.
• System services are part of
backbone and platform
Performance
• Power management, reconfiguration,
load migration, fault detection and
recovery, data collection and analysis
NOC Platform Chip
ASIC
SW
Thickness of service layers
38
NOC Platform development [2]
• Scaling problem
– How big NOC is needed? What are the application area requirements?
• Region definition problem
– What kind of regions are needed? What kind of interfaces between
regions? What are the capacity requirements for the regions?
• Resource design problem
– What is needed inside resources? Internal computation type and internal
communication?
• Application mapping flow problem
– What kind of languages, models and tools must be supported? How to
validate and test the final products?
39
NOC Application Development [2]
• Mapping problem
– How to partition applications for NOC resources? How to allocate
functionality effectively? Is the performance adequate? Is the resource
usage in balance?
• Optimisation problem
– How to perform global optimisation of heterogenuous applications? How
to define right optimisation targets? How to utilise application/resource
type specific tools?
• Validation problem
– Are the contraints met? Are the communication bottlenecks or power
consumption hot spots? How to simulate 10000 GIPS system? How to test
all applications?
40
Methods & Tools [2]
• Analysis of applications
(characterisation)
– analysis of complexity,
computation type,
communication requirement,
storage, etc.
– for scaling, region and resource
type selection, and application
mapping
– Different abstraction levels:
workload model, application
model, execution model
• Validation of decisions
– network simulations at various
abstraction levels (effects of
mapping)
• Estimation of quality
characteristics
– global vs. local optimisation of
the system
• SW architecture vs. HW
architecture
– computation vs. engine
• Development support
– virtual execution platforms for
application developers
– integration of existing design
tools for resource level design
41
Conclusions [2]
• Development of NOC systems will be a huge effort
– reuse in all levels is a must
• reuse of architecture, hardware and software in product
• reuse of different languages, methods, tools and practices during
development
• Backbone, platform, system based design methodology apporach
– provides variability and performance
• Analysis, decision, estimation and validation methods are the
cornerstones of NOC development
– complexity, functionality, workload vs. capacity, performance, efficiency
42
References
1.
2.
3.
Kari Tiensyrjä ([email protected]), Axel Jantsch “NOCARC: Network On Chip Architectures
(Poster)” Department of Microelectronics and Information Technology, Royal Institute of
Technology, Stockholm, Sweden
Juha-Pekka Soininen (VTT Electronics Oulu, Finland), “Part V: A NOC Design Methodology”
NOCARC project, System on Chip workshop, villach, Austria, 17.9.2001
N. D. Gohar, Ahmed Hemani, “National ICT R&D Fund Proposal / Application for Technical
Development and Research Grant”
43
Thank You.