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 4
DTSTART;TZID=America/New_York:20201111T114000
DTEND;TZID=America/New_York:20201111T120000
UID:submissions.supercomputing.org_SC20_sess201_ws_ia107@linklings.com
SUMMARY:Reducing Queuing Impact in Irregular Data Streaming Applications
DESCRIPTION:Workshop\n\nReducing Queuing Impact in Irregular Data Streamin
 g Applications\n\nTimcheck, Buhler\n\nThroughput-oriented streaming applic
 ations on massive data sets are a prime candidate for parallelization on w
 ide-SIMD platforms, especially when inputs are independent of one another.
  Many such applications are represented as a pipeline of compute nodes con
 nected by directed edges. Here, we study applications with irregular data 
 flow, i.e., those where the number of outputs produced per input to a node
  is data-dependent and unknown a priori. Moreover, we target these applica
 tions to architectures (GPUs) where different nodes of the pipeline execut
 e cooperatively on a single wide-SIMD processor.\n\nTo promote greater SIM
 D parallelism, irregular application pipelines can utilize queues to gathe
 r and compact multiple data items between nodes. However, the decision of 
 introducing a queue between two nodes must trade off benefits to occupancy
  against costs associated with writing intermediate values. Moreover, once
  queues are introduced to an application, their relative sizes impact the 
 frequency with which the application switches between nodes, incurring sch
 eduling and context-switching overhead.\n\nThis work examines two optimiza
 tion problems in our model. First, we consider which pairs of successive n
 odes in a pipeline should have queues between them to maximize overall app
 lication throughput. Second, given a fixed total budget for queue space, w
 e consider how to choose the relative sizes of inter-node queues to minimi
 ze the frequency of switching between nodes. We formulate a dynamic progra
 mming approach to the first problem and give an empirically useful approxi
 mation to the second that allows for a closed-form solution. Finally, we v
 alidate our theoretical results using real-world irregular streaming compu
 tations.\n\nRegistration Category: Workshop Reg Pass
END:VEVENT
END:VCALENDAR