A methodology for efficient multiprocessor system-on-chip software development [Elektronische Ressource] / Jianjiang Ceng

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2011
• Nombre de lectures: 13
• Poids de l'ouvrage: 2 Mo

Extrait

A Methodology for Efficient Multiprocessor
System-on-Chip Software Development
Von der Fakulta¨t fu¨r Elektrotechnik und Informationstechnik
der Rheinisch–Westf¨alischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades
eines Doktors der Ingenieurwissenschaften
genehmigte Dissertation
vorgelegt von
M.Sc.
Jianjiang Ceng
aus Zhejiang/China
Berichter: Univ.-Prof. Dr. rer. nat. Rainer Leupers
Univ.-Prof. Dr.-Ing. Gerd Ascheid
Tag der mu¨ndlichen Pru¨fung: 28.04.2011
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨gbar.Contents
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 MPSoC Software Development Challenge . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Programming Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Application Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Mapping and Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Architecture Modeling and Simulation . . . . . . . . . . . . . . . . . . . . 7
1.2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Related Work 11
2.1 General Purpose Multi-Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 General Purpose Graphics Processing Unit . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Embedded Multi-Processor System-on-Chip . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 MPCore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 IXP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.3 OMAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.4 CoMPSoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.5 SHAPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.6 Platform 2012 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 HOPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.8 Daedalus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.9 MPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.10 TCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Methodology Overview 35
3.1 MPSoC Application Programming Studio (MAPS) . . . . . . . . . . . . . . . . . 35
3.1.1 Application Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Architecture Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.3 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.4 Control/Data Flow Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.5 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
iii Contents
3.1.6 Scheduling & Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.7 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.8 High-Level Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.9 Target MPSoC Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.10 Integrated Development Environment . . . . . . . . . . . . . . . . . . . . . 42
3.2 Contribution of This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Architecture Model 45
4.1 Performance Estimation and Architecture Model . . . . . . . . . . . . . . . . . . . 45
4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Processing Element Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.1 C Compilation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.2 Operation Cost Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.3 Computational Cost Estimation . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Architecture Description File. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.1 Processing Element Description . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.2 Architectural Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5 Profiling 55
5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2 Profiling Process Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3 Trace Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3.1 LANCE Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3.2 Instrumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3.3 Profiling Runtime Library . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.3.4 Trace File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.4 Post-Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4.1 IR Profile Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4.2 Source Profile Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.4.3 Call Graph Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6 Control/Data Flow Analysis 71
6.1 Control Flow Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.2 Statement Control Flow Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3 Statement Control/Data Flow Graph . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.3.1 Data Dependence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.4 Weighted Statement Control/Data Flow Graph . . . . . . . . . . . . . . . . . . . 76
6.4.1 Node Weight Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.4.2 Control Edge Annotation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.4.3 Data Edge Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7 Partitioning 79
7.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.2 Task Granularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.3 Coupled Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.3.1 CB Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
iiContents iii
7.3.2 Schedulability Constraint. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.3.3 Data Locality Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.4 CB Generation and WSCDFG Partitioning . . . . . . . . . . . . . . . . . . . . . . 86
7.4.1 WSCDFG Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.4.2 Partition Optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.4.3 CAHC Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.5 Global Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.6 User Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8 High-Level Simulation 99
8.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2 MVP Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
8.3 MVP Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.3.1 Virtual Processing Element . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.3.2 Generic Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.3.3 User Interface and Virtual Peripheral . . . . . . . . . . . . . . . . . . . . . 107
8.4 Software Tool Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.4.1 Execution Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.4.2 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.5 Debug Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
9 Case Study 115
9.1 JPEG Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.1.1 TCT Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.1.2 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .