- : Ms Word, Ms Word Format
- : 100 Pages
- : ₦5000
- : 1-5 Chapters
- Click to DOWNLOAD Materials
A TOOL FOR THE SIMULATION OF STREAM PROCESSING TASKS ON TWO DIMENSIONAL PROCESSOR ARRAYS
ABSTRACT
A tool for the simulation of stream processing tasks on two dimensional processor arrays is developed in this work. The tool, a Many-core Energy and Latency Estimator (MELE) has provided abstractions from the many design constraints facing application developers on Many-core platforms. A set of models have been designed to improve the programmer’s ability to iteratively map data flow applications to the target machine. Included in the model set are; an application model, which presents the resource requirements of the application to the virtual machine; a machine model, which collects the parameters of the modeled machine, and makes use of a set of performance functions in calculating the delay in carrying out tasks; and an energy model, which uses a set of energy functions to calculate the energy cost of carrying out tasks. The set of models transforms the application mapped to the virtual machine into its Intermediate Representation. An Abstract Interpreter has been developed to run on the Ptolemy II modeling platform as a means of returning feedback from the Intermediate Representation to the programmer. Two case studies have been used to showcase the use of MELE in analyzing the mapping of data flow applications. The case studies have also been used to explain how a rank based system can arrive at the most suitable mapping of an application to the processor. Results from the case studies show that the use of a greater number of cores in the processing does not necessarily result in the highest ranked mapping. Also, separate mappings arrive at their steady state processing cost values at different times. Based on these results, developers can now simulate the performance of several processors using one generic tool and arrive at the optimum mapping for an application.
Keywords: Many-core, Energy, Latency, Generic, Hardware, Ranking
1.6 Thesis Organization 9
CHAPTER 2
2.0 Literature Review 11
2.1 Candidate Hardware Platforms 11
2.1.1 Application Specific Integrated Circuit (ASIC) 13
2.1.2 Field Programmable Gate Arrays (FPGAs) 15
2.1.3 System on a Chip (SOC) 16
2.1.4 Multi-Core Processors 16
2.1.5 Many-Core Processors 20
2.1.5.1 Ambric’s Am2045 Chip 20
2.1.5.2 Tilera’s Tile 64 Chip 23
2.2 Streams and Stream Processing Systems 25
2.3 Data Flow Model 27
2.3.1 Synchronous Dataflow (SDF) Model 28
2.3.1.1 Notations and Definitions in SDF 29
2.3.2 Kahn Process Network (KPN) 32
2.3.3 Process Network (PN)
2.4 Ptolemy II 33
2.5 Language Developments 34
2.6 Scheduling 37
2.7 Related work 39
2.7.1 CACTI 39
2.7.2 WATTCH 40
2.7.3 ORION 2.0 41
2.7.4 MCPAT 41
2.7.5 RAW modeling 42
CHAPTER 3
3.0 Methodology 44
3.1 The Design Specification 45
3.2 The Software Requirements Specification 47
3.3 The Target Processor 49
3.4 System Description 50
3.5 The Model Set of the Model Transformer 55
3.5.1 The Application Model 56
3.5.2 The Machine Model 57
3.5.2.1 The Performance Functions 61
3.5.3 The Energy Model 65
3.5.3.1 Core Energy Consumption 66
3.5.3.2 Interconnection Network Energy Consumption 68
3.5.3.3 Energy Functions 70
3.6 The intermediate Representation 75
3.7 The abstract Interpreter 78
3.7.1 How the Abstract Interpreter Works 79
CHAPTER 4
4.0 Results and Discussion 81
4.1 Running Ptolemy II 82
4.2 Machine Configuration 84
4.3 Case Study A 86
4.3.1 Placement for Case Study A 87
4.3.2 Running the Application 88
4.3.3 Results for Case Study A 89
4.4 Case Study B 96
4.4.1 Placement for Case Study B 98
4.4.2 Results for Case Study B 99
4.5 Discussion 101
4.5.1 Contention and Stalls 101 4.5.2 Steady State Convergence Time 102
CHAPTER 5
5.0 Conclusion 105
5.1 Contribution to Knowledge 106
5.2 Limitations to Set Goals 108 5.3 Suggestions for Further Work 109
REFERENCES 111
Appendix A 123
Appendix B 124 Appendix C 138 Appendix D 140 Appendix E 144 Appendix F 158
CHAPTER ONE
1.0 INTRODUCTION
Modern stream processing applications demand real – time performance and a low power budget. The term “stream” means the continuous one directional flow of data in any format. Stream applications are characterized by complex algorithms that must process data
deterministically, at very high rates. This means that processing has to cope with the rate at which data is being captured. This places constraints on application developers on embedded platforms such as digital camcorders, compact digital television sets, handheld medical imaging equipment, mobile phones and base station equipment, where stream applications are typically found. Media applications on these devices involve thousands of operations per pixel in order to achieve high output resolutions, making power consumption a major constraint in a basket of constraints such as size, flexible implementations, real time performance, cost and a fast development time. An added constraint is the ability to provide for additional functionalities on short notice.
However, battery power is not increasing at the same pace as computational requirements, making this a source of worry for engineers. This is particularly a problem, given that the traditional demarcation lines between these devices are increasingly blurred, resulting in devices that are no longer function specific. This convergence of functions on a particular platform, encouraged by the need to provide users with as much functionality as possible on a single device, and a race to produce the ultimate handheld device, accentuates the pressure presented by size and power constraints. Furthermore, governments and environmental activists are stepping up the pressure in an effort to reduce the aggregate power demands of embedded applications. This has led to tough standards for energy efficiency, placing further pressure on designers to seek increasingly efficient solutions.
This work proposes that the solution lies with implementing these applications in software on programmable processors. Software is easier to design, develop, maintain and upgrade without scrapping expensive hardware. Even though programmable processors are lagging behind the efficiency curve, recent developments show that they are gradually catching up. Emerging parallel processor technologies, given the right programming environment, give us the possibility of limiting the gap in performance of programmable processors to within a few steps of what can be achieved with Application Specific Integrated Circuits (ASICs).
As for cost, using commercially available, off the shelf hardware platforms like general purpose programmable processors, has the potential of limiting cost profiles significantly by encouraging hardware reuse. For instance, the Non Recurring Engineering (NRE) cost of ASICs has been consistently on the rise as silicon density and computational complexities rise with each new process generation. As of today, an ASIC design project costs upwards of $30 million [Butts 2008] and it keeps rising with improvements in process technology. Consequently, the number of new ASIC designs fell by 50% between 2000 and 2003 [LaPedus 2007] . Also, life time cost of maintaining software on programmable platforms will be far outstripped by the cost of hardwired solutions like ASICs and Field Programmable Gate Arrays (FPGAs). Improvements in algorithms can always be countered with software upgrades instead of freezing outdated algorithms in hardware.
ASICs are also taking a longer time to develop with increasing algorithmic complexity and increasing silicon density. The hardware design productivity gap that existed ever since 2003 has been widening [Smith 2003] . This has huge design implications in today’s fast changing electronics and embedded systems industry. Taking too long to introduce a new product can result in a shrink in market share for a particular implementation. The same happens when it takes too long to upgrade existing products. So, time to market constraints have to be mitigated by using adaptable programmable solutions. However, most emerging programmable platforms lack the tools that will allow these platforms take advantage of time to market constraints especially when it comes to the fast moving Digital Signal Processing (DSP) domain.
This is why development tools are needed to allow for easy simulation of the application on the selected many – core platform thereby providing developers with an easy means of getting feedback early in the development process. This will also reduce design cost and save time by improving on software design productivity.
1.1 BACKGROUND INFORMATION
High performance stream processing systems demand real-time performance and low power expenditures.Traditionally, time and power constraints were satisfied using hardwired logic in the form of ASICs and FPGAs. Such technology made it possible to meet the performance and power requirements of real time embedded applications at the cost of limited flexibility and a high development cost.
As it stands today, ASICs are 50 times more efficient than programmable processors [Dally & Others, 2008] . This efficiency gap makes ASICs the solution of first choice for high-volume embedded systems where performance and energy efficiency are of primary concern and where unit costs resulting from high Non Recurring Engineering (NRE) costs can be driven down because of high volumes. However, algorithms and standards are evolving at a faster pace than ever before and freezing them in hardwired logic exacerbates the flexibility problem. Also, as signal processing applications get even more complex, it is necessary to have a more generalised hardware implementation, while restricting the implementation of the (more) complex algorithms to software.
Solutions are therefore being developed in the form of highly parallel, much more power efficient programmable processors. These processors have in some cases reduced the efficiency gap between ASICs and programmable processors to within 3 times. They incorporate tens if not hundreds of distributed processing units, otherwise regarded as cores, which have the potential of increasing to the thousands in the not too distant future. Typically they communicate through Network on Chip (NOC) communication structures and maintain localized memories in the cores. These processors are now increasingly regarded as many – core processors and they are distinct from their multi-core counterparts because of their distributed memory structure.
However, to be able to use these parallel machines efficiently, application developers need tools that will assist them in exploiting these increasing number of cores. These tools must be domain specific in order to make the most impact. They should allow developers to easily develop applications on many – core processors, mapping those applications to specific cores, and parallelizing parts of the application in ways that can allow them to run faster, while also being able to tune down the speed of cores that are not heavily used, thereby, scaling down the overall energy consumed by the application.
1.2 PROBLEM STATEMENT
The dramatic increase in the number of cores on a single chip has increased the complexity of developing software on such parallel platforms. Going by the predictions of the international technology road map 2007 [ITRS, 2007] and 2011 [ITRS, 2011] , the complexity in program development will rise well into the next decade. Therefore, there is need to develop means of abstracting the complexities of program development on such machines.
The problem for this work is to develop a suitable portable platform for abstracting these problems from the developer. At the moment, tools for many-core processors are mostly proprietary in nature, making it very difficult to develop applications without the support of the manufacturer. It restricts the ease of carrying out comparative analysis across processors and configurations at the earliest stage of product development.
These challenges can be overcome with a portable system which will allow the developer to use several machine configurations before arriving at a particular processor configuration based on simulation results.
1.3 OBJECTIVES
The research objective is to develop a tool for analyzing the dynamic execution cost of Digital Signal Processing tasks on many-core processors in terms of latency and energy consumption. This comprises of the following tasks:
- Develop a set of models that describe a virtual many-core machine. The set will include; a machine model which will use a set of abstract performance functions to calculate the cost of performing computation blocks in the cores of the machine in terms of latency; an energy model which will use a set of abstract energy functions to calculate the cost of performing computation blocks in the cores of the machine in terms of energy; and an application model which will be used to provide the machine with the resource needs of the
application in terms of processing power and
- Introduce Intermediate Representation that will concretize the actions of the models and at the same time, generate the code for the cores based on a particular mapping.
- Provide a means of returning feedback to the developer. This should make it possible for the developer to iteratively improve the schedule in a way that will allow timing constraints to be met at the least energy budget.
1.4 JUSTIFICATION OF STUDY
The need for a portable tool for ranking mappings on many – core machines cannot be over emphasized. As the number of cores per processor grows, so does the programming complexity.
A tool that will provide a developer with the right feedback, upfront, can dramatically reduce the cost and time budgets of an application. This will make it easier to wade through the maze of possibilities that this architecture can offer.
Also, it can serve as a training tool, helping to deepen students understanding of the nature of parallel processing in general and stream processing in particular. For instance, a tool like this can open up the possibilities of reclaiming slack time from some cores as long as timing constraints can still be met, thereby saving more energy.
1.5 SCOPE OF WORK
This work is intended to address a few of the problems involved in designing streaming applications on a class of programmable processors often called many – core processors. There can be several implementations of many – core processors; however, this work will be limited to two dimensional processor arrays (also known as Tiled processors), which means, an n x m array of processors on a Network on
Chip (NOC) fabric.
This work will look at the stream processing domain. In this domain, data to be processed is regarded as data-flows or streams. However, it will be restricted to the Synchronous Data flow (SDF) model of computation (which is a subset of the streaming domain).
Finally, it is expected that the resulting tool will assist in the development of streaming applications by providing an environment for experimenting with the design thereby providing feedback on the feasibility of the design based on two very important non – functional constraints, namely:
- Latency
- Energy
This work will not attempt to map the tasks onto the processor. However, the tool will provide the developer with the capacity to experiment with several mappings while using the expected feedback to iteratively search for the most acceptable mapping.
1.6 THESIS ORGANISATION
This thesis is organized as follows: Chapter 1 presents the introduction, highlighting the background information, motivation, problem statement, research objectives, justification and scope of work. Chapter 2 provides a review of the literature that summarizes work that has already been done in the field, both in terms of the technology and related implementations. In Chapter 3, the layout of the model set that abstracts the details of the many-core and streaming application is introduced and discussed. Details of the functions that calculate the cost of decisions made are provided as well as the Intermediate Representation. The Abstract Interpreter that will be used to return feedback to the developer is also provided. In Chapter
4, an outline of how abstract interpretation can be carried out on the Ptolemy II platform is discussed together with a discussion based on two experimental mapping case studies. The aim is to show how a rank based feedback tuning can be carried out using a performance and energy cost estimation system. Chapter five presents the conclusion of this thesis.
A TOOL FOR THE SIMULATION OF STREAM PROCESSING TASKS ON TWO DIMENSIONAL PROCESSOR ARRAYS
