A MILP approach to DRAM access worst-case analysis. (July 2022)

• Record Type: Journal Article
• Authors: Andreozzi, Matteo; Frangioni, Antonio; Galli, Laura; Stea, Giovanni; Zippo, Raffaele
• Is Part Of: Computers & operations research. Volume 143(2022)
• Publication Date: 2022-07
• Subjects: Mixed integer linear programming -- Worst-case analysis -- Scheduling -- Network-calculus; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105774
• Languages: English
• ISSNs: 0305-0548

Abstract

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 crucial information for future memory design improvements. Highlights: Exact worst-case delay in COTS DRAM can be computed as a MILP optimum. Worst-case delay yields compositional service curves for complex system design. Upper and lower bounds can be inferred from sample MILP solutions. Bounds fed back to the MILP greatly improve solution efficiency. Optimal solutions describe worst-case scenarios, useful for hardware design.