Roeland, D (2000) Scheduling in Multi-X : a performance evaluation. Master's Thesis / Essay, Computing Science.
|
Text
Infor_Ma_2000_DRoeland.CV.pdf - Published Version Download (2MB) | Preview |
Abstract
This master's thesis project is carried out at Ericsson Utvecklings AB, the research and development centre for Ericsson's Network Core Products. One of the major products of Ericsson Utvecklings AB is the AXE telephone switching system. The need for capacity in AXE switches is increasing at an unexpected rate due to new services like ISDN, GSM and the Internet. To keep up with competition, AXE's central processor's capacity needs to be doubled every third year. A number of projects have been started in order to cope with this problem. One of them is the Gemini project, which will propose an architecture based on commercially available components. One of the main prerequisites for Gemini's new architecture is backward compatibility with existing AXE software. On the long term, the capacity of Gemini's architecture will not be sufficient. The Multi-X project investigates methods of utilising execution on parallel processors, with Gemini's architecture as a premise. The focus of Multi-X is a new technique called task-level speculative execution. This technique is a form of implicit parallelism; parallelism is extracted from conventional imperative and unmodified code. With speculative execution, assumptions are made on the data and control flow in a program. By looking ahead in the instruction stream, instructions can be run in parallel. Instructions have to be rolled back, i.e. undone, on incorrect assumptions. Instruction-level parallelism is a commonly known technique used in most of today's modern processors. By the beginning of the 1990s, several studies proved the limitations of performanceincrease using instruction-level parallelism. These limitations are mainly caused by imperfect predictions of future data and control flow. Since mid 1990s a trend can be observed to not only exploit parallelism at a finegrained instruction level, but simultaneously also at a coarse-grained task level. The Multi-X project has developed a prototype to prove the concept of task-level speculative execution on a multiprocessor system based on Gemini's architecture. This prototype is still being improved, tested and modified. No results on performance increase are available yet. As a final phase in Multi-X, the prototype can be optimised in a number of ways. One optimisation is task scheduling, where scheduling is defined as 'the process of deciding what task to execute where and when'. This thesis will focus on the consequences in performance of different task distribution principles. In this thesis project, the Multi-X prototype is modelled and an optimal scheduling algorithm is defined in order to calculate an upper bound on performance. Furthermore, three practical scheduling algorithms are proposed and a simulator is developed to investigate their performance. Live-recorded telephone switch traffic is used as input data to calculations and simulations. The three proposed practical ways of scheduling are first-come-firstserve scheduling, function-based scheduling and source-based scheduling. With first-come-first-serve scheduling the next task is simply sent to an arbitrary idle processor. This algorithm is currently used in the Multi-X prototype. Function-based scheduling is an attempt to avoid unnecessary rollbacks by examining what functions a task will execute. Source-based scheduling is an attempt to map individual subscribers to individual processors in order to exploit cache-affinity and diminish inter-task dependencies. The simulations performed in this thesis project are the first on the Multi-X concept where all relevant parameters are taken into account. The concept is proved to hold theoretically, whereas a critical note is made concerning the feasibility of a real implementation. Scheduling should really be seen as an optimisation. Only a moderate performance increase can be accomplished with scheduling. First-come-first-serve scheduling performs very well, even compared to optimal scheduling. Ideas from function-based scheduling can be used additionally to improve performance even more. Source-based scheduling results in poor performance, mainly caused by load imbalance. A lot of issues remain to be tested, simulated and analysed. This thesis is only one step forward towards a better understanding of a multiprocessor architecture running telephone switch traffic.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Computing Science |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:29 |
| Last Modified: | 15 Feb 2018 07:29 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/8827 |
Actions (login required)
 |
View Item |