Post-Doctoral Research Visit F/M Can a two-dimensional address space improve the spatial locality of memory accesses?

Inria
February 05, 2023
Contact:N/A
Offerd Salary:Negotiation
Location:N/A
Working address:N/A
Contract Type:Other
Working Time:Negotigation
Working type:N/A
Ref info:N/A

2022-05618 - Post-Doctoral Research Visit F/M Can a two-dimensional address space improve the spatial locality of memory accesses?

Contract type : Fixed-term contract

Level of qualifications required : PhD or equivalent

Fonction : Post-Doctoral Research Visit

About the research centre or Inria department

The Inria Rennes - Bretagne Atlantique Centre is one of Inria's eight centres and has more than thirty research teams. The Inria Center is a major and recognized player in the field of digital sciences. It is at the heart of a rich R&D and innovation ecosystem: highly innovative PMEs, large industrial groups, competitiveness clusters, research and higher education players, laboratories of excellence, technological research institute, etc.

Context

This post-doctoral project is funded by the French National Research Agency (ANR) as part of the Maplurinum project. The Maplurinum project revisits the foundations of computer architecture and operating systems for cloud computing and high-performance computing, to better manage the growing heterogeneneity of hardware components. A 128-bit address space is considered as one of the possible solutions to achieve this goal.

This post-doctoral project focuses on some of the architectural implications of a 128-bit address space. However, instead of representing an address as a single value like existing instruction-set architectures (ISAs) do, we consider the possibility to represent an address as two 64-bit values: an X coordinate and a Y coordinate. Our intuition is that the data structures used by programmers are often multi-dimensional, and that mapping a multi- dimensional data structure onto a one-dimensional address space degrades the spatial locality of memory accesses. Spatial locality is an empirical, qualitative property of programs stating that memory addresses that are spatially close to each other are likely to be accessed during the same period of time. This property is heavily exploited by high-performance microarchitectures. Nevertheless, there exists workloads processing a large amount of data with poor spatial locality. Performance-wise, these workloads suffer from long-latency memory accesses. The main objective of this post- doctoral project is to answer the following question: can a two-dimensional (2D) address space improve the spatial locality of memory accesses?

To study a 2D address space, ideally, one would need to create a new ISA, adapt a compiler and an operating system to this ISA, invent a new microarchitecture and write a simulator to evaluate performance. This would be a daunting task, far beyond the time and resources this project can afford. The main objective of this post-doctoral project is precisely to tell whether continuing in that direction would be worth the effort.

To get around this chicken-and-egg problem, we have developed a C++ library called MXY allowing to write algorithms in a language resembling the C programming language. Executing an algorithm written with MXY generates an address trace which can then be analyzed. The current, early version of MXY just emulates a conventional one-dimensional memory. With adequate modifications, MXY will be able to simulate a 2D address space.

Assignment

Spatial locality is a loosely defined qualitative principle. Although a few attempts have been made to define spatial locality in a quantitative manner (see the references below), there is currently no consensus in the computer architecture community as to the best way to do it. Before diving into 2D address spaces, it will probably be necessary to understand what spatial locality means in the context of a multi-dimensional address space and define a suitable spatial locality metric. Once a metric has been defined and validated, the researcher will search for some realistic data structures and algorithms that can be used as benchmarks. Using MXY, the researcher will experiment with different ways to use a 2D address space, seeking to maximize spatial locality. If this exploration is successfull, the researcher will consider the implications of a 2D address space on virtual-to-physical address translation and on the microarchitecture, particularly caches and hardware prefetching.

References:

  • R. B. Bunt and J. M. Murphy, "The measurement of locality and the behaviour of programs", The Computer Journal, vol. 27, no. 3, 1984.
  • J. Weinberg, M. O. McCracken, E. Strohmaier and A. Snavely, "Quantifying Locality In The Memory Access Patterns of HPC Applications", ACM/IEEE Supercomputing Conference (SC), 2005.
  • R. C. Murphy and P. M. Kogge, "On the Memory Access Patterns of Supercomputer Applications: Benchmark Selection and Its Implications", IEEE Transactions on Computers, vol. 56, no. 7, july 2007.
  • X. Gu, I. Christopher, T. Bai, C. Zhang and C. Ding, "A Component Model of Spatial Locality", International Symposium on Memory Management (ISMM), 2009.
  • S. Gupta, P. Xiang, Y. Yang and H. Zhou, "Locality principle revisited: A probability-based quantitative approach", Journal of Parallel and Distributed Computing, vol. 73, no. 7, july 2013.
  • Main activities

    The researcher will focus on the proposed research topic and will try to answer the question asked in the title. The proposed research plan is a suggestion and may be subject to modifications if science dictates. The researcher is expected to be autonomous and will have freedom in determining the best course of action to answer the title's question.

    Skills

    The candidate must have a PhD in computer science, specialized in a computer architecture topic or in a topic very closely related to computer architecture, such as compilation. Besides having a solid knowledge of classical computer architecture, the candidate should be able to question established conventions. Proficiency in C++ is required to modify MXY.

    Benefits package
  • Subsidized meals
  • Partial reimbursement of public transport costs
  • Possibility of teleworking (90 days per year) and flexible organization of working hours
  • Partial payment of insurance costs
  • Remuneration

    monthly gross salary amounting to 2746 euros

    General Information
  • Theme/Domain : Architecture, Languages and Compilation
  • Town/city : Rennes
  • Inria Center : Centre Inria de l'Université de Rennes
  • Starting date : 2023-09-01
  • Duration of contract : 2 years
  • Deadline to apply : 2023-02-05
  • Contacts
  • Inria Team : PACAP
  • Recruiter : Michaud Pierre / pierre.michaud@inria.fr
  • About Inria

    Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.

    Instruction to apply

    Please submit online : your resume, cover letter and letters of recommendation eventually

    For more information, please contact pierre.michaud@inria.fr

    Defence Security : This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.

    Recruitment Policy : As part of its diversity policy, all Inria positions are accessible to people with disabilities.

    Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.

    From this employer

    Recent blogs

    Recent news