How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem

DOI10.1007/S11081-020-09507-WzbMATH Open1473.90180arXiv1910.00170OpenAlexW3028651114MaRDI QIDQ2245689FDOQ2245689

Authors: Raviv Gal, Brian Irwin, Bilal Saleh, Avi Ziv, Eldad Haber 

Publication date: 15 November 2021

Published in: Optimization and Engineering (Search for Journal in Brave)

Abstract: The testing and verification of a complex hardware or software system, such as modern integrated circuits (ICs) found in everything from smartphones to servers, can be a difficult process. One of the most difficult and time-consuming tasks a verification team faces is reaching coverage closure, or hitting all events in the coverage space. Coverage-directed-generation (CDG), or the automatic generation of tests that can hit hard-to-hit coverage events, and thus provide coverage closure, holds the potential to save verification teams significant simulation resources and time. In this paper, we propose a new approach to the CDG problem by formulating the CDG problem as a noisy derivative free optimization (DFO) problem. However, this formulation is complicated by the fact that derivatives of the objective function are unavailable, and the objective function evaluations are corrupted by noise. We solve this noisy optimization problem by utilizing techniques from direct optimization coupled with a robust noise estimator, and by leveraging techniques from inverse problems to estimate the gradient of the noisy objective function. We demonstrate the efficiency and reliability of this new approach through numerical experiments with an abstract model of part of IBM's NorthStar processor, a superscalar in-order processor designed for servers.

Full work available at URL: https://arxiv.org/abs/1910.00170

Recommendations

• Approximating low-dimensional coverage problems
• On directed covering and domination problems
• On directed covering and domination problems
• A practical heuristic for maximum coverage in large-scale continuous location problem
• From the species problem to a general coverage problem via a new interpretation
• On the \(k\)-path cover problem for cacti
• The generalized maximum coverage problem
• Conditional covering: greedy heuristics and computational results
• Algorithms for solving the conditional covering problem on paths

zbMATH Keywords

inverse problemshardware verificationderivative free optimizationcoverage directed generationstatistical parameter estimation

Mathematics Subject Classification ID

Nonlinear programming (90C30) Methods of quasi-Newton type (90C53) Derivative-free methods and methods using generalized derivatives (90C56)

Cites Work

• Implicit filtering
• Numerical Optimization
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• The NEWUOA software for unconstrained optimization without derivatives
• Introduction to Derivative-Free Optimization
• Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
• Estimating Computational Noise
• Global optimization by multilevel coordinate search
• Derivative-free optimization: a review of algorithms and comparison of software implementations
• Title not available (Why is that?)
• Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
• Adaptive System Optimization Using Random Directions Stochastic Approximation
• An introduction to data analysis and uncertainty quantification for inverse problems

Cited In (1)

• Secant penalized BFGS: a noise robust quasi-Newton method via penalizing the secant condition

Uses Software

• NEWUOA
• IMFIL
• MultiMin
• MCS

This page was built for publication: How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2245689)