BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210402T160554Z
LOCATION:Track 2
DTSTART;TZID=America/New_York:20201112T161500
DTEND;TZID=America/New_York:20201112T164500
UID:submissions.supercomputing.org_SC20_sess208_ws_pmbsf107@linklings.com
SUMMARY:Developing Models for the Runtime of Programs with Exponential Run
 time Behavior
DESCRIPTION:Workshop\n\nDeveloping Models for the Runtime of Programs with
  Exponential Runtime Behavior\n\nBurger, Nguyen, Bischof\n\nIn this paper,
  we present a new approach to generate runtime models for programs whose r
 untime grows exponentially with the value of one input parameter. Such pro
 grams are, e.g., of high interest for cryptanalysis to analyze practical s
 ecurity of traditional and post-quantum secure schemes. The model generati
 on approach on the base of profiled training runs is built on ideas 
 realized in the open source tool Extra-P, extended with a new class of mod
 el functions and a shared-memory parallel simulated annealing approach to 
 heuristically determine coefficients for the model functions. Our ap
 proach is implemented in the open source software SimAnMo (Simulated Annea
 ling Modeler).  We demonstrate on various theoretical and synthetic, pract
 ical test cases that our approach delivers very accurate models and reliab
 le predictions, compared to standard approaches on x86 and ARM architectur
 es. SimAnMo is also employed to generate models of four codes which are em
 ployed to solve the so-called shortest vector problem. This is an importan
 t problem from the field of lattice-based cryptography. We demonstra
 te the quality of our models with measurements for higher lattice dimensio
 ns, as far as it is feasible. Additionally, we highlight inherent problems
  with models for algorithms with exponential runtime.\n\nRegistration Cate
 gory: Workshop Reg Pass
END:VEVENT
END:VCALENDAR