Optimization Online


A MILP Approach to DRAM Access Worst-Case Analysis

Matteo Andreozzi(matteo.andreozzi***at***arm.com)
Antonio Frangioni(antonio.frangioni***at***unipi.it)
Laura Galli(laura.galli***at***unipi.it)
Giovanni Stea(giovanni.stea***at***unipi.it)
Raffaele Zippo(raffaele.zippo***at***unifi.it)

Abstract: The Dynamic Random Access Memory (DRAM) is among the major points of contention in multi-core systems. We consider a challenging optimization problem arising in worst-case performance analysis of systems architectures: computing the worst-case delay (WCD) experienced when accessing the DRAM due to the interference of contending requests. The WCD is a crucial input for micro-architectural design of systems with reliable end-to-end performance guarantees, which is required in many applications, such as when strict real-time requirements must be imposed. The problem can be modeled as a mixed integer linear program (MILP), for which standard MILP software struggles to solve even small instances. Using a combination of upper and lower scenario bounding, we show how to solve realistic instances in a matter of few minutes. A novel ingredient of our approach, with respect to other WCD analysis techniques, is the possibility of computing the exact WCD rather than an upper bound, as well as providing the corresponding scenario, which represents a crucial information for future memory design improvements.

Keywords: Mixed-Integer Linear Program, Worst-Case Analysis, Network-Calculus , Scheduling

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Working Paper, University of Pisa, Italy. April 2021.

Download: [PDF]

Entry Submitted: 04/30/2021
Entry Accepted: 04/30/2021
Entry Last Modified: 04/30/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society