Modeling and avoiding execution interferences

Research topic and goals

The recent architectural evolutions of the interconnection network pose two main challenges: first, the community is proposing new topologies (Besta and Hoefler 2014), (Tuncer, Leung, and Coskun 2015); and second, the network is now unique within the machine. Sharing a unique, multi-purpose interconnection network begets complex interactions between running applications, and it has a strong impact on the performances. More precisely, one can identify two main types of interleaved flows: flows induced by data exchanges for computations, and I/O flows. This collaboration aims at designing new scheduling algorithms that better take into account the challenges of interconnecting compute nodes with a unique and multiple-purpose network.

Results for 2015/2016

Blue~Waters’s network topology makes scheduling at the machine’s scale a real challenge (Enos et al. 2014). We studied the execution of jobs on Blue~Waters, and derived a generic model of such machines (Bleuse et al. 2017). For example, the new topologies are built using local heterarchic (contrary of hierarchical) networks that are interconnected by a low depth hierarchy (Besta and Hoefler 2014), (Tuncer, Leung, and Coskun 2015). The constraints arise from the distribution of the heterogeneous nodes within the topology. Heterogeneity may come from various architecture of computing nodes, or mixed workloads of computing and analysis, or nodes dedicated to I/O. We do not take such constraints into account in a quantitative manner. We rather translate these constraints in geometric properties: allocations have to be convex (in order to limit interferences between different jobs), or need to embed specific designated nodes.

Results for 2016/2017

The model proposed last year has been welcomed with interest by the scheduling community. The convexity constraint (with respect to the underlying network topology) allows to tackle some interferences. Constraining applications to be allocated near the I/O nodes they are using might be a way to completely remove interferences.

We refined the model, by precising geometric constraints/metrics of interest: contiguity, convexity, compacity, proximity, and locality (missing reference). We studied the algorithmic complexity of various instantiations (notably enforcing convexity and locality constraints at the same time). We proposed fast approximation algorithm for these instantiations.

Visits and meetings

Raphaël Bleuse (INRIA) spent 3 weeks at NCSA in winter 2015

Impact and publications

  1. Bleuse, Raphaël, Sascha Hunold, Safia Kedad-Sidhoum, Florence Monna, Grégory Mounié, and Denis Trystram. 2017. “Scheduling Independent Moldable Tasks on Multi-Cores with GPUs.” IEEE Transactions on Parallel and Distributed Systems. IEEE. doi:10.1109/TPDS.2017.2675891. 
    @article{BleuseR2017Scheduling,
  note = {in print},
  author = {Bleuse, Rapha{\"{e}}l and Hunold, Sascha and Kedad{-}Sidhoum, Safia and Monna, Florence and Mouni{\'{e}}, Gr{\'{e}}gory and Trystram, Denis},
  title = {{Scheduling Independent Moldable Tasks on Multi-Cores
  	       with GPUs}},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  volume = {},
  number = {},
  pages = {},
  year = {2017},
  doi = {10.1109/TPDS.2017.2675891},
  publisher = {IEEE},
  issn = {1045-9219},
  language = english
}

Future plans

Some simple instantiations of the model have been studied. The next step is to study, by simulation with traces of Blue~Waters, how these algorithms behave at scale: what is the cost of enforcing these constraints? While the algorithms studied so far have proven performance guarantees in worst case, we are interested in studying fast heuristics, and comparing them to the guaranteed algorithms.

The convexity constraint might be a too strong constraint when combined with the locality constraint: how can we relax the convexity constraint while keeping good properties?

On the other hand, given a requested amount of computing nodes, many convex shapes are valid allocations. We are interested in studying how to choose a shape in order to better exploit the machines. Similarly, we are also interested in studying if allocating more resources than requested may simplify the allocation phase without losing too much computation power.

References

  1. Tuncer, Ozan, Vitus J. Leung, and Ayse K. Coskun. 2015. “PaCMap: Topology Mapping of Unstructured Communication Patterns Onto Non-Contiguous Allocations.” In Proceedings of the 29th ACM on International Conference on Supercomputing, 37–46. ICS 15. New York, NY, USA: ACM. doi:10.1145/2751205.2751225. 
    @inproceedings{TuncerO2015PaC,
  address = {{New York, NY, USA}},
  booktitle = {{Proceedings of the 29th ACM on International Conference on Supercomputing}},
  publisher = {{ACM}},
  series = {{ICS 15}},
  author = {Tuncer, Ozan and Leung, Vitus J. and Coskun, Ayse K.},
  title = {{PaCMap: Topology Mapping of Unstructured Communication Patterns Onto Non-contiguous Allocations}},
  pages = {37--46},
  year = {2015},
  doi = {10.1145/2751205.2751225}
}
  2. Besta, Maciej, and Torsten Hoefler. 2014. “Slim Fly: A Cost Effective Low-Diameter Network Topology.” In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 348–59. SC 14. Piscataway, NJ, USA: IEEE Press. doi:10.1109/SC.2014.34. 
    @inproceedings{BestaM2014Slim,
  address = {{Piscataway, NJ, USA}},
  booktitle = {{Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis}},
  publisher = {{IEEE Press}},
  series = {{SC 14}},
  author = {Besta, Maciej and Hoefler, Torsten},
  title = {{Slim Fly: A Cost Effective Low-diameter Network Topology}},
  pages = {348--359},
  year = {2014},
  doi = {10.1109/SC.2014.34}
}
  3. Enos, Jeremy, Gregory H. Bauer, Robert Brunner, Sharif Islam, M. Steed, D. Jackson, and R. Fiedler. 2014. “Topology-Aware Job Scheduling Strategies for Torus Networks.” Cray User Group. 
    @article{EnosJ2014Topology,
  author = {Enos, Jeremy and Bauer, Gregory H. and Brunner, Robert and Islam, Sharif and Steed, M. and Jackson, D. and Fiedler, R.},
  title = {{Topology-Aware Job Scheduling Strategies for Torus Networks}},
  journal = {{Cray User Group}},
  year = {2014}
}