Complexity analysis of scheduling algorithms for parallel computing
| industrial collaborators: | ARM Ltd |
| academic collaborators: | University of Nottingham |
| initiated : | 2009/10/03 |
| last updated: | 2010/04/27 |
 |
 |
Project staff and support
Jakub Marecek (Intern, University of Nottingham)Danny Kershaw (Company Supervisor, ARM)
Edmund K. Burke and Andrew J. Parkes (Academic Mentors, University of Nottingham)
Lorcan Mac Manus (Technology Translator, Industrial Mathematics KTN)
This Internship project was carried out at ARM Ltd, in conjunction with University of Nottingham. It was part of the KTN's Industrial Mathematics Internships Programme, co-funded by EPSRC. Start date: October 2009; duration: 6 months.
Summary
In a modern mobile phone, there are a number of specialised processors. Standards mandating application acceleration (OpenCL) and broadband wireless communications (LTE, LTE Advanced) are currently undergoing particularly rapid development. Scheduling is essential for the performance of application accelerations. Efficient use of bandwidth in modern wireless communication is offset by the complexity of signal decoding in the Multiple Input Multiple Output (MIMO) setting, where there are multiple transmitting and multiple receiving antennas operating concurrently in the frequency band. The internship focused on these areas:
- Understanding the theoretical complexity of scheduling in OpenCL accelerators;
- Designing scheduling algorithms for OpenCL accelerators;
- Designing algorithms for MIMO signal decoding.
In OpenCL accelerators, we have modelled the problem of scheduling work-load, and established the EXP-Hard complexity of obtaining the best possible policy. Subsequently, we have designed policies, which are asymptotically optimal under certain simplifying assumptions. Finally, we have designed data structures making it possible to implement the policies efficiently. We have provided a prototype implementation in C++.
MIMO signal decoding is known to be NP-Hard, when channel estimates are given. We have suggested a new approach to the problem, which is based on the interior point methods for second-order cone programming and conic mixed integer rounding cuts. Preliminary implementations of the approach have been developed in Matlab and C.
Outcomes
The research contributions of this work include: models of scheduling in OpenCL accelerators; proofs of EXP-Hardness of certain models; work towards proofs of k-EXP-Hardness of other models; new fully-dynamic data structures for maintaining trees, which in turn support a range of diameter-like queries.
The engineering contributions of this work include: the development of a prototype of a scheduler for OpenCL accelerators; the development of early prototypes of interior point methods for second-order cone programming; and separation routines for conic mixed integer rounding cuts, suitable for implementation in hardware.
Benefits
Through this internship project, the student acquired a better appreciation of engineers’ approach to problem-solving.
"The internship has given me an opportunity to learn about a number of challenging problems at Arm Ltd. It is great to see mathematics and advanced algorithm design used to tackle real-life problems," said Jakub Marecek, Intern (University of Nottingham).
"Results from this project exceeded expectations. In Jakub we found a very able intern who taught us how to apply recent results from his specialist branch of mathematics to problems we at ARM face in engineering solutions used in everyday products such as mobile phones. My thanks to all at the Maths KTN for their role in making this possible," said Danny Kershaw, Industrial supervisor (ARM).
"It was highly rewarding to see mathematical techniques from operational research being successfully applied to important problems outside of the traditional scope of OR," said Andrew Parkes, Academic supervisor (University of Nottingham).