Titulo Estágio
Instruction scheduling strategies to reduce memory requirements
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
DEI/UC
Enquadramento
Register allocation and instruction scheduling are problems that have been central in the development of compilers. Compilers use register allocation to assign temporary variables to processor registers or to memory, and instruction scheduling orders instructions to improve computational throughput. Allocation and scheduling have a significant impact on the performance of the generated code.
Traditionally, this problem has been considered as computationally infeasible, so heuristic algorithms that sacrifice optimal solutions in favor of lower complexity have been favoured. These algorithms have been applied separately to the two problems.
However, combinatorial optimization approaches have been emerging in the last couple of decades to solve these problems as a single problem. In general, these approaches are slower, but more flexible to changes, and can be used to generate optimal code. These approaches are interesting as both problems are interdependent (e.g. the solution for one will affect the other).
We are interested in looking at approaches that consider the interdependency of both problems, with an emphasis on how instruction scheduling can affect the number of registers needed to allocate a given set of computed information. More specifically, BNP Paribas is looking at using this central compiler problem, to be able to infer what is the best sequence to compute a set of functions (instructions scheduling), that minimizes the size of the arrays that we need to have in memory to hold results without rerunning computation (arrays are our equivalent to registers).
Objetivo
1. Review the state of the art on the subject (include possibly relevant articles from other fields)
2. Propose and implement an alternative approach not existing in the state of the art, or a technique based on the state of the art approaches.
3. Study and validate its effectiveness with artificially generated data.
4. Back-test its effectiveness on BNP Paribas Quantitative Research scale.
5. (optional) Participate to go live in production at BNP Paribas
Plano de Trabalhos - Semestre 1
- State of the art review
- Development of a framework to analyse the approaches (generating artificial data and evaluating the score of each approach to a large test set). Note: the student can opt to use and adapt a framework of his/hers preference
- Proposal on the technique to use: Exact approach vs Approximated approach / Deterministic vs Non-Deterministic approach: Implementation of a mockup and a small study should be conducted to support this decision.
- Elaboration of an intermediate thesis
Plano de Trabalhos - Semestre 2
- Review of the 1st semester decisions accordingly to the intermediate defense feedback.
- Implementation of the selected approach and conduct the primary study. (We expect a review of the approach according to the results of these study).
- Conduct the study at BNP Paribas scale (with data provided by the Quantitative Research team)
- (Depending on the success of the previous steps) Presentation of the work for the BNP Paribas Quantitative Research Team in Paris)
- Write the final thesis report
Condições
Depending on results (and pending approval):
The student might be invited to Paris or London to present the work done to BNP Paribas Quantitative Research Team management.
Orientador
Pedro Correia
pedro.correia@bnpparibas.com 📩