Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$42,000.00

""Online algorithms, paging and multicore architectures (CMP)""

FY 2016-17

Summary
Online algorithms and analysis is the study of computational problems in which final, irrevocable decisions must be made under incomplete or partial information. Its applications range from memory management and scheduling, to exploration of a disaster area, to planning the location of service centers in a growing city. Numerous failed attempts to model and predict the desired characteristics of a ""good"" online algorithm in practice have been made; however this goal has yet to be fully realized. We believe that this research is now near fruition. Indeed, recently we introduced a model for paging algorithms which answered a long standing question on the observed superiority of the Least Recently Used (LRU) heuristic. We will study in particular better measures for the performance of paging, list update, bin packing and buffered packet routing. A second objective of this research is to study paging and caching algorithms for multicore architectures. We have shown thus far that this problem is NP-complete for the offline version; that the main challenge is in the assignment of cache sizes; and that issues of fairness of execution are crucial to performance. We will propose novel practical algorithms for paging in chip multiprocessors with matching theoretical guarantees. Equally important, we are developing a theoretical model for modern multicore architectures that includes issues of synchronization, interprocessor communication, paging, and ease of programming and analysis. The established model of serial computation (RAM) is an excellent tradeoff of the parameters above, and suitable extensions have been developed for I/O bound models. In contrast, for parallel computations no single model has stood out, with the PRAM and/or the BSP model of Valiant being the leading candidates for a replacement. We will study an update of the PRAM model but with a bounded number of processors. Thus we benefit from previous PRAM work while avoiding its more vexing characteristics. This research aims to introduce a new multicore model which is both amenable to study and accurately reflects the physical hardware, which is a key step for the development of the next generation of efficient algorithms.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
217254-2012
Name nom
LopezOrtiz, Alejandro
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
5
Nb partie
5
Application title
""Online algorithms, paging and multicore architectures (CMP)""
Keyword
NSERC
Application summary
Online algorithms and analysis is the study of computational problems in which final, irrevocable decisions must be made under incomplete or partial information. Its applications range from memory management and scheduling, to exploration of a disaster area, to planning the location of service centers in a growing city. Numerous failed attempts to model and predict the desired characteristics of a ""good"" online algorithm in practice have been made; however this goal has yet to be fully realized. We believe that this research is now near fruition. Indeed, recently we introduced a model for paging algorithms which answered a long standing question on the observed superiority of the Least Recently Used (LRU) heuristic. We will study in particular better measures for the performance of paging, list update, bin packing and buffered packet routing. A second objective of this research is to study paging and caching algorithms for multicore architectures. We have shown thus far that this problem is NP-complete for the offline version; that the main challenge is in the assignment of cache sizes; and that issues of fairness of execution are crucial to performance. We will propose novel practical algorithms for paging in chip multiprocessors with matching theoretical guarantees. Equally important, we are developing a theoretical model for modern multicore architectures that includes issues of synchronization, interprocessor communication, paging, and ease of programming and analysis. The established model of serial computation (RAM) is an excellent tradeoff of the parameters above, and suitable extensions have been developed for I/O bound models. In contrast, for parallel computations no single model has stood out, with the PRAM and/or the BSP model of Valiant being the leading candidates for a replacement. We will study an update of the PRAM model but with a bounded number of processors. Thus we benefit from previous PRAM work while avoiding its more vexing characteristics. This research aims to introduce a new multicore model which is both amenable to study and accurately reflects the physical hardware, which is a key step for the development of the next generation of efficient algorithms.