

        <cite>Bryce</cite>
      <time>0:00</time>
      <p>
          For   anybody   who&#39;s   familiar   with   NumPy   style   broadcasting,   where   when   you&#39;re   working   with   two   arrays   of   different   already   sh   It&#39;s   Aridi,   not   Artie   Artie   sounds   like   Ariana   Grande&#39;s   cousin.   Alright,   we&#39;re   we&#39;re   cooking   here.
      </p>

        <cite>Conor</cite>
      <time>0:12</time>
      <p>
          We   might   have   explained   the   scatter   completely   wrong.
      </p>

        <cite>Bryce</cite>
      <time>0:15</time>
      <p>
          We&#39;re   just   two   b   two   men   sitting   here   talking   into   uh   ChatGPT.
      </p>

        <cite>Conor</cite>
      <time>0:20</time>
      <p>
          What   I   should   have   been   saying   is   gather,   but   I&#39;m   not   even   confident   about   that   because   my   confidence   is   shot   because   I   totally   messed   up   the   description   of   an   algorithm.
      </p>

        <cite>Bryce</cite>
      <time>0:27</time>
      <p>
          So   get   out   to   yourself,   man.   We&#39;re   cooking   here.   And   so   once   again,   I   shall   tilt   it   windmills   on   my   quest   to   figure   out   whether   we   can   do   this   on   a   single   pass   algorithm.   Uh   is   it   poorly   named?
      </p>

        <cite>Conor</cite>
      <time>0:39</time>
      <p>
          Maybe   it&#39;s   actually   it&#39;s   actually   well   named   and   scatter   is   poorly   named.   The   point   being   is   I   don&#39;t   like   the   asymmetry   between   scattered   and   permutation   iterator.
      </p>

        <cite>Bryce</cite>
      <time>0:46</time>
      <p>
          When   you   launch   a   CUDA   kernel,   you   have   to   specify   how   many   blocks   you&#39;re   running   with.   This   this   microphone&#39;s   a   little   bit   waterproof,   right?   I   don&#39;t   know.   Okay.
      </p>

        <cite>Conor</cite>
      <time>1:23</time>
      <p>
          We   continue   our   conversation   from   last   week   about   the   replicate   algorithm   and   two   other   algorithms,   scatter   and   gather.   Alright,   folks,   so   right   off   the   bat,   I   do   need   to   apologize.   In   this   video,   for   the   majority   of   it,   I   refer   to   the   scatter   algorithm,   when   really   what   I   meant   was   gather,   and   I   got   incredibly   confused.   We   rectify   this   at   some   point   in   the   conversation.   Scatter   is   an   algorithm   that   exists   in   Thrust,   doesn&#39;t   exist   in   the   C   standard   library,   but   I&#39;m   sure   it   exists   in   uh   other   libraries   and   languages.   You&#39;re   given   a   sequence   and   uh   like   uh   your   your   data   sequence,   which   could   be,   you   know,   numbers,   whatever,   any   type,   and   then   you&#39;re   given,   I   believe   it&#39;s   indices,   and   I&#39;m   gonna   feel   bad   if   uh   this   is   incorrect,   but   I&#39;m   almost   positive   it&#39;s   a   sequence   of   integers   uh   that   uh   correspond   to   indices   that   are   between   zero   and   one   minus   the   length   of   your   data   sequence.   And   uh,   or   that&#39;s   what   the   values   of   the   the   indices   have   to   be,   obviously.   It   has   to   be   a   valid   index.   And   the   length   of   your,   I   believe   it&#39;s   what   they   call   um   an   index   map,   um,   the   length   of   that,   alright,   perfect.   Let   us   sit.   Is   this   gonna   be   wet   though?
      </p>

        <cite>Bryce</cite>
      <time>2:37</time>
      <p>
          Although   this   is   a   it&#39;s   a   theater,   which   is   not   open.
      </p>

        <cite>Conor</cite>
      <time>2:40</time>
      <p>
          It&#39;s   clear   clearly   a   restaurant,   but   hopefully   just   no   one   will   come   and   serve   us.   Although   this   is   wet   as   well.   These   ones   are   dry.
      </p>

        <cite>Bryce</cite>
      <time>2:47</time>
      <p>
          These   ones   are   well,   these   can&#39;t   possibly   be   wet.
      </p>

        <cite>Conor</cite>
      <time>2:50</time>
      <p>
          They   are   But   these   tables   are   not   clean,   so   I   think   this   is   totally   fine.   No   one&#39;s   gonna   come   and   serve   us   here.   A   little   dark,   but   that&#39;s   okay.   We   got   a   nice   view.   Um   so   the   length   of   your   in   so   you&#39;ve   got   your   data,   and   you&#39;ve   got   an   index   map   that   can   be   any   length   you   want.   So   if   the   length   of   our   data   is   three   ABC,   we   can   have   uh   index   map   that   consists   of   just   a   single   one,   and   what   it   does   is   it   scatters   the   element   at   index   one   to   your   output   sequence.   So   if   you   scatter,   if   if   you   so   scatter,   you&#39;ve   got   your   data,   and   you&#39;ve   got   an   index   map,   which   is   a   sequence   of   indices.   And   scatter   basically   goes,   it   iterates   through   the   indices   and   then   copies   them   to   so   it&#39;s   like   a   copy   if,   except   that   a   copy   if   just   takes   a   predicate   and   then   it   it&#39;s   a   stable   copy   where   the   relative   orders   are   the   same,   obviously,   because   you&#39;re   just   getting   rid   of   some   of   the   values,   and   then   anything   that   corresponds.   This   is   not   how   permutation   iterator   works.   You&#39;re   just   gonna   permutation   iterator.   I&#39;m   I&#39;m   trying   to   explain   that   sequence,   if   for   those   that   aren&#39;t   familiar   with   uh   thrust   sequence,   thrust   sequence   is   the   equivalent   of   stdiota,   the   algorithm   in   C.   It   generates   incrementing   integers   starting   from   a   value,   typically   zero.   And   in   C20,   we   added   the   view   iota,   which   does   the   exact   same   thing   just   lazily.   In   thrust,   the   two   names   for   these   things   are   thrust   sequence   and   the   thrust   counting   iterator.   The   same   way   that   there&#39;s   a   relationship   between   sequence   and   counting   iterator,   there&#39;s   a   relationship   between   scatter   and   the   permutation   iterator.   So   scatter   takes   your   data   and   an   index   map   and   it   copies   from   the   indices   that   and   the   values   that   correspond   to   those   to   an   output   sequence.   So   if   you&#39;ve   got   ABC   and   uh   one,   you   just   get   the   character   B.   If   you&#39;ve   got   ABC   and   3,   2,   1,   you   end   up   reversing   your   sequence.   If   you   have   ABC   1,   2,   3,   3,   2,   1,   your   output   sequence   is   ABC   C   B   A.   You&#39;re   basically,   you   know,   it&#39;s   pretty   straightforward.   A   permutation   iterator,   potentially   better   named   as   the   scatter   iterator,   is   the   same   thing,   but   you&#39;re   just   bundling   an   iterator   that   points   to   your   data   and   an   iterator   that   points   to   this   index   map.   That&#39;s   it.   And   so   if   you&#39;re   trying   to   do   any   kind   of   operation   lazily   that   is   a   specialization   or   some   form   of   permutation,   you   can   do   it   with   a   permutation   iterator.   You   need   to   reverse   a   sequence,   you   can   do   that   with   a   permutation   iterator.   You   need   to   cycle   a   sequence,   you   can   do   that   with   a   permutation   iterator.   You   need   to   replicate   a   sequence,   you   can   do   that   with   a   permutation   iterator.   A   lot   of   the   times,   it&#39;s   not   the   most   performant   way   to   do   this   stuff   because   of   the   fact   that   a   permutation   iterator   is   so   generic,   there&#39;s   some   overhead   there.   But   the   point   being   is   that   a   permutation   iterator,   it&#39;s   is   it   poorly   named?   Maybe   it&#39;s   actually   it&#39;s   it&#39;s   actually   well   named   and   scatter   is   poorly   named.   The   point   being   is   I   don&#39;t   like   the   asymmetry   between   scatter   and   permutation   iterator.   And   anyways,   this   is   all   to   say   that   the   very   first   implementation   of   the   replicate   uh   integer   overload   just   made   a   call   to   the   permutation   iterator   where   the   index   map   was   just   cycling   indices.   Which,   how   do   you   do   cycling   indices   in   thrust?   You   can   just   do   a   counting   iterator   composed   with   a   transform   iterator   that   does   modulus   over   the   length   of   your   sequence.   So   you   generate   the   numbers,   you   know,   if   you   want   to   uh   replicate   it.   Well,   I   guess.   Oh,   actually,   that&#39;s   a   good   point.   Oh   no,   right,   because   n   is   the   same   for   everything,   right?   So   if   you&#39;re   trying   to   replicate   everything   three   times,   you   do   a   counting   iterator,   zero   to   nine   or   zero   to   eight   inclusive,   and   then   you   do   modulus   three,   and   then   you&#39;re   gonna   end   up   with   zero   one   two,   zero,   one   two,   zero,   one   two   as   your   index   map,   and   that   is   the   uh   equivalent   of   a   replicate   when   you   apply,   you   know,   uh   a   copy   if   using   that   per   so   that   actually   that&#39;s   a   that&#39;s   a   great   way   of   framing   it.   Scatter   can   be   implemented   and   probably   is   implemented,   well   actually   I   don&#39;t   know,   I   don&#39;t   know   that,   as   thrust   copy   if   with   a   permutation   iterator.   That&#39;s   just   what   scatter   is.   Anyways,   I&#39;m   gonna   stop   talking.
      </p>

        <cite>Bryce</cite>
      <time>7:05</time>
      <p>
          You   did   a   good   job   of   explaining   it.   I   I   I   would   um   yeah,   for   the   for   the   integer   version,   I   mean   I   guess   you   you   can   just   think   of   it   as   as   just   being   that   you&#39;re   you&#39;re   you&#39;re   um   you&#39;re   copying   from   the   array,   but   uh   like   like   you&#39;ve   I   I   have   an   array   of   length,   you   know,   n   um   and   then   I   um   I   want   to   replicate   each   element   m   times.   So   then   I&#39;ve   got   an   array   of   length   n   times   m,   and   when   I   index   into   that   array   of   length   n   times   m,   I&#39;m   indexing   into   the   original   array   of   length   n,   and   I&#39;m   just   moduloing   so   that   I   wrap   around.   And   that&#39;s   that&#39;s   that&#39;s   it.   And   that&#39;s   probably   the   m   fastest   way   to   do   it.
      </p>

        <cite>Conor</cite>
      <time>7:53</time>
      <p>
          Except   I   totally   messed   up.   As   some   of   you   are   screaming   in   your   head   right   now,   that   doesn&#39;t   make   any   sense   because   it   doesn&#39;t.   What   I   just   described   is   cycling.   If   you&#39;re   replicating,   you   want   to   be   doing   the   opposite   of   modulo,   which   is   integer   division.   Right.   So   you   want   to   go   from   zero   to   eight   inclusive,   not   to   zero   one   two   zero   one   two   zero   one   two   because   that   results   in   ABC,   ABC,   ABC,   which   is   cycling.   You   want   to   have   zero   zero   zero   one   one   one   two   two   two,   which   is   integer   division,   and   then   you   end   up   with   A,   B,   B,   B,   C,   C,   C.
      </p>

        <cite>Bryce</cite>
      <time>8:21</time>
      <p>
          Yeah,   yeah,   it&#39;s   sorry,   that&#39;s   I   I   should   have   also.   But   but   um   but   and   permutation   iterator   should   boil   down   to   just   being   the   integer   division.   Although   you   were   saying   earlier   that   you   hit   some   perfection,   right?
      </p>

        <cite>Conor</cite>
      <time>8:35</time>
      <p>
          Permutation   iterator   doesn&#39;t   do   any   of   that   work   for   you.   You   have   to   give   it   the   index   map.   So   it   can   be   it   can   be   completely   a   random   sequence,   right?   If   you   want   to   do   a   shuffle.
      </p>

        <cite>Bryce</cite>
      <time>8:44</time>
      <p>
          But   so   for   the   index   map,   you&#39;re   passing   in   some   sort   of   transform   iterator   that   does   the   division?
      </p>

        <cite>Conor</cite>
      <time>8:49</time>
      <p>
          Exactly.   So   the   the   transform,   it&#39;s   a   counting   iterator   with   a   transform,   so   it&#39;s   counting   iterator,   piped   or   whatever,   to   a   transform   iterator   that   does   the   integer   division,   and   that   iterator,   those   that   iterator   that   is   the   composition   of   those   two   iterators,   you   pass   to   a   permutation   iterator.   And   so   if   you   want,   you   you   could   just   do   like   a   random   shuffle   by   generating   a   random   sequence   of   indices,   and   then   that   you   know,   call   a   copy   if   with   that   permutation   iterator,   and   that   would   be   a   shuffle,   right?   You   can   do   anything   almost   with   a   permutation   iterator.   You   can   do   a   copy   with   a   permutation   iterator   where   your   index   map   is   just   a   counting   iterator.   You   wouldn&#39;t   want   to   do   it   that   way,   because   that&#39;s   ridiculous.   But   like   the   point   being   is   that   like   the   permutation   iterator   is   like   the   most   powerful   of   the   iterators.   Like   if   you   think   we&#39;ve   got   constant   iterator,   we&#39;ve   got   counting   iterator,   we&#39;ve   got   transform   iterator.
      </p>

        <cite>Bryce</cite>
      <time>9:34</time>
      <p>
          To   to   be   uh   an   important   clarification   I   just   realized   is   we   mentioned   a   replicate   iterator   before,   and   we   mentioned   two   overloads   of   replicate.   The   replicate   iterator   only   exists   for   the   integer   version,   right?
      </p>

        <cite>Conor</cite>
      <time>9:44</time>
      <p>
          Wait,   wait.   There&#39;s   no   replicate   iterator.   There&#39;s   two   overloads   of   the   replicate   function.   One   like   they   both   take   the   data   sequence,   one   takes   an   integer   and   the   other   one   takes   an   array.
      </p>

        <cite>Bryce</cite>
      <time>9:54</time>
      <p>
          But   but   but   sorry,   to   clarify   further,   one   could   imagine   writing   a   replicate   iterator   for   the   integer   version   um   because   you   can   do   that   lazily.   I   don&#39;t   think   you   can   do   it   for   the   array   version.
      </p>

        <cite>Conor</cite>
      <time>10:06</time>
      <p>
          Yes,   if   I   understood   what   you   just   said,   the   integer   version   is   lazy.   Yeah.   The   array   version   is   not.
      </p>

        <cite>Bryce</cite>
      <time>10:11</time>
      <p>
          And   the   the   reason   the   reason   for   that   is   because   for   the   array   version,   it&#39;s   trivial   a   priori   to   know   ahead   of   time   like   the   length   of   the   sequence.   And   so   then   thus   to   know   like   the   array   version.   The   integer   version.   It&#39;s   it&#39;s   it&#39;s   trivial   to   know   ahead   of   time   the   length   of   the   sequence.   And   it&#39;s   important   to   know   the   length   of   the   or   not   just   about   knowing   the   length   of   the   sequence,   it&#39;s   trivial   ahead   of   time   to   know   the   placement   of   you   know   of   where   every   element&#39;s   gonna   be   in   the   output.   Whereas   when   you&#39;ve   got   variable   size   uh   replicates,   you   don&#39;t   necessarily   like   the   it&#39;s   no   longer   an   independent   problem   um,   you   know,   the   the   of   where   each   element   is   in   the   output,   and   that   makes   it   some   form   of   scan,   um,   some   form   of   copy   of.   And   and   and   but   you   mentioned   earlier   running   into   perf   issues   with   the   permutation   iterator.   Was   that   the   case?   Or   I   I   think   that   the   implementation   you   just   described   should   be   the   impl   the   optimal   implementation.
      </p>

        <cite>Conor</cite>
      <time>11:07</time>
      <p>
          Using   the   permutation   iterator,   which   is   a   very   generic   utility,   is   I   have   found   a   lot   of   the   times   comes   with   overhead   because   we&#39;re   using   a   permutation   iterator   to   do   something   more   specific.
      </p>

        <cite>Bryce</cite>
      <time>11:24</time>
      <p>
          Yeah,   yeah,   yeah.
      </p>

        <cite>Conor</cite>
      <time>11:24</time>
      <p>
          What   we   really   want   is   a   custom   iterator   that   doesn&#39;t   incur   the   overhead   of   something   so   generic.   And   so   I   a   lot   of   the   times   things   like   cycle   iterator   and   cycle   iterator,   replicate   iterator,   a   couple   others,   I   would   all   I   would   always   implement   in   terms   of   the   permutation   iterator   because   that   that   was   the   utility   there.   But   one   time   I   was   profiling   my   work   versus   Jax,   which   I   consider   or   uh   anecdotally   in   my   profiling,   I&#39;ve   uh   the   the   Jax   jitting   typically   is   the   best   for   this   kind   of   stuff.   And   there   was   one   example   that   was   uh   Jax   was   beating   the   work   that   I   was   working   on.   And   so   I   started   doing   some   tuning,   and   I   found   like   three   different   times   switching   the   cycle   iterator   to   basically   implement   a   bespoke   thing   that   didn&#39;t   rely   on   permutation   iterator   and   doing   the   same   thing   for   the   replicate   iterator,   each   of   those   led   to   like   a   performance   improvement.   And   I   was   kind   of   surprised,   but   it   it   does   like   anytime   you&#39;re   reaching   for   something   that   is   not   not   in   terms   of   like   a   generic   reduction,   because   you&#39;re   just   passing   a   binary   operation,   but   something   like   a   permutation   iterator   that   has   to   be   capable   of   more,   similar   to   when   we   talk   about   using   reduced   by   key,   if   you   want   to   do   like   a   row-wise   reduction,   reaching   for   reduced   by   key,   which   can   handle   variable   length   segments,   whereas   the   rows   of   a   matrix   always   have   the   same   length.   Anytime   you&#39;re   doing   that,   it   shouldn&#39;t   be   surprising   that   it   incurs   some   kind   of   overhead.
      </p>

        <cite>Bryce</cite>
      <time>12:48</time>
      <p>
          So   uh   but   it   it   is   weird   because   um   because   it&#39;s   just   this   like   iterator   abstraction,   um,   it   should   just   melt   away.   But   I   I&#39;m   not   I&#39;m   not   shocked   to   hear   that   you   did   run   into   perf   issues   with   it,   because   we&#39;re   talking   about   an   operation   that   uh   uh   we&#39;ve   talked   about   two   operations   like   the   the   cycle   and   and   replicate,   both   of   which   boil   down   to   doing   uh   integer   division   or   integer   modulo.   Um   and   so   it&#39;s   possible   that   the   kernel   ends   up   being   uh   like   integer   throughput   constrained   or   maybe   even   register   constrained,   and   that   uh   some   of   the   abstraction   cost   of   permutation   iterator,   which   again   should   be   able   to   boil   away,   um   uh   may   still   be   present.   I   guess   it&#39;s   i   I   I   I   I   think   it&#39;s   maybe   also   possible   that   that   the   permute   the   use   of   permutation   iterator   throws   off   uh   like   vectorization,   uh,   and   maybe   that&#39;s   causing   problems.   But   um,   but   anyways,   uh   it   would   be   interesting   to   look   more   into   that,   but   but   I   think   we   digress.
      </p>

        <cite>Conor</cite>
      <time>13:59</time>
      <p>
          Yeah,   and   I   think   what&#39;ll   happen   here,   folks,   is   we   recorded   the   episode   in   Aarhus   last.   And   so   I   think   we&#39;ve   we   figured   out   that   you   were   gonna   be   listening   to   that   on   October.   Let&#39;s   let&#39;s   check   the   calendar,   folks.   We&#39;ve   got   too   many   apps,   the   calendar&#39;s   way   down   there.   You   will   have   already   listened   to   the   Orhus   episode   on   October   5th.   We   are   going   to   actually,   so   wait,   this   episode&#39;s   gonna   come   out   on   the   12th.   So   maybe   I   was   gonna   say   we&#39;re   we   plan   on   recording   at   least   once   when   we&#39;re   at   NDC   Tech   Town.   We   might   do   it   on   the   Wednesday   night.   They&#39;ve   got   like   a   little   social   afterwards,   and   it&#39;ll   our   our   workshops   will   be   done,   your   talk   will   be   done.
      </p>

        <cite>Bryce</cite>
      <time>14:37</time>
      <p>
          So   I   think   probably   It&#39;ll   be   interesting   to   see   whether   uh   either   of   us   still   have   a   voice   after   two   days   of   eight-hour   courses.
      </p>

        <cite>Conor</cite>
      <time>14:45</time>
      <p>
          Yeah,   it&#39;s   uh   it&#39;s   a   good   point.   Pending   that   we   have   voices,   we   will   record   uh   probably   in   a   couple   days   on   the   Wednesday,   the   first   day   of   NDC   Tech   Town.   And   so   the   the   seven   episodes   ago   when   I   mentioned   that,   like,   oh,   remind   me   that   we   got   to   talk   about   replicate,   is   that   it   is,   I   think,   one   of   the   most   interesting   uh   algorithms   that   I&#39;ve   implemented   because   it   is   it   has   such   an   interest   like   the   going   from   the   integer   overload,   which   is   pretty   trivially   done   and   not   only   done   but   done   lazily,   to   the   array   overload,   it&#39;s   compl   it&#39;s   almost   a   completely   different   algorithm   because   you   can&#39;t   do   it   lazily,   or   you   definitely   can&#39;t   do   all   of   it   lazily.   And   uh   so   think   about   it.   You   know,   Bryce   already   gave   you   a   hint,   a   scan   is   involved,   which   it&#39;s   almost   become   oh,   I   guess   it&#39;s   the   integer.   I   think   it   is   just   I   think   it   is   strictly   just   run   length   decode.   I   mean,   but   run   run   length   decoding   though   is   cheating.
      </p>

        <cite>Bryce</cite>
      <time>15:38</time>
      <p>
          How   is   it   cheating?   It&#39;s   the   s   it&#39;s   the   same   inputs.   It&#39;s   gotta   be   just   run   length   decoding.
      </p>

        <cite>Conor</cite>
      <time>15:42</time>
      <p>
          I   guess   it   is   just   run   length   decoding.   Well,   Bryce   is   currently   looking   up.   Does   Cub   have   a   run   length   decode?
      </p>

        <cite>Bryce</cite>
      <time>15:49</time>
      <p>
          Okay,   now   I   gotta   look   at   how   it   works.
      </p>

        <cite>Conor</cite>
      <time>15:50</time>
      <p>
          Yeah,   what&#39;s   the   API?
      </p>

        <cite>Bryce</cite>
      <time>15:52</time>
      <p>
          It   takes   run   value   and   it   it   takes   values   uh   and   uh   as   an   array   of   n   and   it   takes   uh   lengths   as   an   array   of   n.
      </p>

        <cite>Conor</cite>
      <time>16:00</time>
      <p>
          But   we&#39;re   still   going   to   talk   about   how   would   you   implement   this   in   thrust   if   you   were   limited   to   using   thrust.
      </p>

        <cite>Bryce</cite>
      <time>16:07</time>
      <p>
          So   run   length   decode   and   cub,   um   it   decodes   into   like   a   window   of   a   limited   size,   and   then   it&#39;s   repeated   until   all   the   runs   have   been   decoded.   I&#39;m   almost   certain   that   the   way   that   Cub   does   it   is   not   gonna   be   the   way   that   you&#39;ve   implemented   it,   because   you   described   implementing   it   in   terms   of   a   scan,   which   sounds   right,   but   I   think   what   Cub   does   is   Cub   picks   a   static   fixed-size   window   um   and   it   starts   with   the   sequence   and   it   decodes,   it   starts   decoding   what   it&#39;s   got   until   the   window   is   filled,   and   then   uh   it   must   write   the   window   to   the   output,   and   then   it   starts   doing   another   window.   Um   why   is   this   optimal?
      </p>

        <cite>Conor</cite>
      <time>16:59</time>
      <p>
          That   doesn&#39;t   sound   very   parallel.
      </p>

        <cite>Bryce</cite>
      <time>17:01</time>
      <p>
          That   does   not   sound   very   parallel,   that   sounds   very   sequential.   This   is   for   the   block   length   one.
      </p>

        <cite>Conor</cite>
      <time>17:05</time>
      <p>
          I&#39;m   gonna   have   to   look   at   what   the   I   would   guess   that   using   a   scan,   you   can   figure   out   where   in   the   data   sequence   the   beginning   of   each   window   uh   decoding   starts.   Because   you   can   you   can   back   that   out   with   a   operation   that   I   will   not   reveal   here,   but   I   I   think   I   think   we&#39;re   essentially   saying   the   same   thing?
      </p>

        <cite>Bryce</cite>
      <time>17:30</time>
      <p>
          Uh   no,   no,   no,   no.   I   think   we&#39;re   essential   so   essentially   we&#39;re   we&#39;ve   come   upon   how   do   you   implement   efficient   GPU   decompression.   So   this   what   I   just   described   is   was   was   for   the   block   run-length   decode.   Alright,   you   you   talk   about   things   while   I   look   at   what   the   uh   the   device-wide   one   does.
      </p>

        <cite>Conor</cite>
      <time>17:46</time>
      <p>
          Bryce   is   deep   reading   GitHub   code.   And   uh   it&#39;s   good   to   be   in   Denmark.   Had   a   lovely   run   today.   We   did   a   long   run.   30k.   Started   off   a   bit   rough   because   I   did   not   eat   anything,   but   then   I   got   a   power   aid   at   the   11k   mark.   Denmark   is   a   very   beautiful   country,   Copenhagen&#39;s   a   very   beautiful   city.   We&#39;ll   definitely   be   back.   Yeah,   beautiful   evening.   So   good   to   be   alive,   folks.   Good   to   be   alive.   Bryce   wants   the   mic.
      </p>

        <cite>Bryce</cite>
      <time>18:14</time>
      <p>
          So   there&#39;s   no   there&#39;s   a   device-wide   run-length   encode   in   Cub.   There&#39;s   no   device-wide   run-length   decode.   There&#39;s   just   this   block   run-length   decode   that   allows   you   to   retrieve   a   window   from   the   run-length   decoded   array.   Which   is   I   guess   makes   sense   if   you   want   to   like   do   block,   if   you   want   to   just   like   process   like   a   chunk,   like   you   want   to   be   able   to   work   with   like   a   fixed-size   chunk   when   you&#39;re   doing   like   CUDA   programming.   But   uh,   okay,   now   I   want   to   hear   I   want   to   hear   how   you   implemented   it.
      </p>

        <cite>Conor</cite>
      <time>18:51</time>
      <p>
          Well,   I   need   to   uh   I   would   need   to   go   back   and   actually   look   because   I   like   I   said,   the   first   time   I   implemented   it,   it   was   incorrect.   But   off   the   top   of   my   head,   whether   this   is   the   actual   implementation,   and   this   may   this   discussion   may   never   see   the   light   of   day   if   it&#39;s   not,   you   do   a   plus   scan   on   the   integers   in   your   integer   array.   Bryce   doesn&#39;t   even   listen   anymore.
      </p>

        <cite>Bryce</cite>
      <time>19:11</time>
      <p>
          I   am,   I   am,   I   am.   What   are   you   doing?
      </p>

        <cite>Conor</cite>
      <time>19:14</time>
      <p>
          He   can   multitask,   he   says.   You   do   a   plus   scan   on   your   integer   array,   and   that   gives   you   the   in   indices   where   each   of   your   uh   decoded   segments   start.
      </p>

        <cite>Bryce</cite>
      <time>19:27</time>
      <p>
          Yes.
      </p>

        <cite>Conor</cite>
      <time>19:28</time>
      <p>
          That&#39;s   the   first   step.   And   then   once   you   have   that,   you   want   to   basically   create   an   index   map   that   corresponds   to   copying   the   first   element   at   index   zero   to   however   many   spots   the   first   integer   represents.   So   if   your   sequence   is   ABC   and   your   index   map   is   one,   two,   three,   you   want   your   resulting   index   map   to   be   zero,   one,   one,   two,   two,   two.   How   do   you   do   this   exactly?   You   want   to.   And   this   is   the   this   is   the   tricky   part.
      </p>

        <cite>Bryce</cite>
      <time>20:03</time>
      <p>
          So   you   have   your   plus   scan   that   is   gonna   give   you   a   scan,   right?
      </p>

        <cite>Conor</cite>
      <time>20:09</time>
      <p>
          Yeah,   well,   I   mean   the   plus   span   g   gives   you   one.
      </p>

        <cite>Bryce</cite>
      <time>20:12</time>
      <p>
          But   the   index   map.   You   can   make   the   index   map   with   a   scan.
      </p>

        <cite>Conor</cite>
      <time>20:17</time>
      <p>
          I   don&#39;t.
      </p>

        <cite>Bryce</cite>
      <time>20:22</time>
      <p>
          You   can   do   a   single   pat   hang   on,   hang   on,   hang   on.   I   think   you   you   just   described   you   need   you   need   to   figure   out   where   you&#39;re   running.
      </p>

        <cite>Conor</cite>
      <time>20:31</time>
      <p>
          I   don&#39;t   remember,   I   don&#39;t   remember.   So   you   do   your   plus   scan   on   your   integer   sequence,   and   that   gives   you   one,   two,   three,   six.
      </p>

        <cite>Bryce</cite>
      <time>20:42</time>
      <p>
          And   those   are   those   are   the   lengths.
      </p>

        <cite>Conor</cite>
      <time>20:45</time>
      <p>
          That&#39;s   technically   the   the   ending   uh   index   plus   one   of   each   of   your   segments.   So   if   you   prefix   that   plus   scan,   if   or   technically,   so   I   mean   in   in   Thrust   this   is   an   exclusive   scan,   but   I   don&#39;t   I   don&#39;t   disambiguate.   I   only   have   one   scan,   and   if   you   want   an   inclusive   scan,   an   exclusive   scan,   you   just   prefix   it   with   a   zero.   So   if   you   add   a   zero   to   your   one,   three,   six,   so   what   one   three   six   to   repeat   and   be   clear,   is   the   result   of   a   one,   two,   three   plus   scan.   So   the   first   element   is   just   your   one,   your   second   element   is   one   plus   two,   your   third   element   is   one   plus   two   plus   three.   So   one,   three,   six.   Add   a   pre-pan   a   zero,   so   you   end   up   with   zero,   one,   three,   six.   We&#39;re   not   gonna   need   the   six,   folks.   That&#39;s   a   little   secret.   And   so   now   what   you   want   to   do   is   you   want   to   do   a   scan.
      </p>

        <cite>Bryce</cite>
      <time>21:38</time>
      <p>
          This   is   a   very   weird   scan.   Wait,   wait,   wait,   wait.
      </p>

        <cite>Conor</cite>
      <time>21:45</time>
      <p>
          I   think   we   might   have   explained   this   we   might   have   explained   the   scatter   completely   wrong.   Because   alright,   I&#39;ll   just   think   out   loud.   I&#39;m   allowed   to   make   a   mistake.   So   right   now   what   I&#39;m   thinking   is   that   with   the   n   minus   one   values   of   your   zero   prefixed   plus   scan.   So   zero,   one,   three,   six,   if   we   drop   the   six,   you   want   to   scatter   the   indices   basically   zero,   one,   and   two   to   those   indices.   You   want   to   scatter   zero   to   the   zero   index,   one   to   the   one   index,   and   two   to   the   three   index,   which   is   a   that   those   indices   you&#39;re   gonna   do   a   path   later   than   you&#39;re   gonna   then   you&#39;re   gonna   do   a   max   scan.   So   if   your   output   sequence   is   gonna   be   six   values   in   length,   you   do   two   scans.   You   do   two   scans,   you   do   a   plus   scan   on   the   integer   sequence,   then   you   do   a   scatter   uh   to   get   the   uh   initial   value   of   each   segment   in   your   output   sequence,   and   then   if   you   do   a   max   scan,   so   what   what   your   output   sequence   it   starts   is   six   zeros,   then   it   starts   as   zero   in   the   first   index,   one   in   the   second   index,   and   then   uh   two   in   the   third   index.   So   there&#39;s   it&#39;s   zero,   one,   zero,   two,   zero,   zero,   I   believe,   if   I   got   I   got   that   right.   And   if   you   do   a   max   scan   on   that   sequence,   basically,   and   you   know   that   because   the   values   are   indices,   so   they&#39;re   always   increasing,   you&#39;re   gonna   end   up   with   zero,   one,   one,   two,   two,   two.   So   the   one   basically   gets   copied   to   everything   up   until   the   two,   and   then   the   max   scan,   the   max   kicks   in   again,   and   the   one   resets   to   a   two,   and   then   everything   after   that   is   a   two.   The   thing   that   I&#39;ve   realized   though   is   that   I&#39;m   pretty   sure.   Well,   actually,   I&#39;m   now   I&#39;m   confused.   A   scatter   might   not   scatter   indices   to   a   destination.   It   it   might   it   might   scatter   the   elements   to   that   index.   We   have   to   look   that   up.   Actually,   in   my   lookup,   I&#39;m   just   gonna   ask   Gemini.   Actually,   we&#39;ll   we&#39;ll   get   Gemini   on   the   pod   right   now.
      </p>

        <cite>Bryce</cite>
      <time>24:03</time>
      <p>
          Write   me   a   kernel   that   does   device-wide   run-length   decoding   using   the   card.
      </p>

        <cite>Conor</cite>
      <time>24:11</time>
      <p>
          What   does   the   algorithm   scatter   in   the   thrust   parallel   algorithms   library   do?
      </p>

        <cite>Bryce</cite>
      <time>24:20</time>
      <p>
          We&#39;re   just   we&#39;re   just   two   p   two   men   sitting   here   talking   into   uh   Chat   GPT.
      </p>

        <cite>Conor</cite>
      <time>24:27</time>
      <p>
          I&#39;m   a   little   bit   surprised   because   in   the   past   it   usually   reads   it   to   me,   and   I   guess   I   click   some   button   that   uh   turned   off   the   live   reading.   But   it   says   the   thrust   scatter   algorithm   in   the   thrust   parallel   algorithm   library   is   a   powerful   and   efficient   parallel   primitive   that   reorders   a   sequence   of   elements.   It   copies   elements   from   a   source   sequence   to   a   destination   sequence,   but   instead   of   a   one-to-one   copy,   it   uses   a   map   to   determine   the   destination   index   for   each   element.   So,   yeah,   it&#39;s   uh   I   I   did   uh   no,   no,   no,   I   I   messed   it   up.   So   it   says   the   essence   is   that   ThrustScatter   performs   the   following.   The   destination   of   the   map   of   the   i   th   index   is   equal   to   the   source   at   the   i-th   index.
      </p>

        <cite>Bryce</cite>
      <time>25:11</time>
      <p>
          Which   means   write   it   again,   but   no   comments   and   make   it   as   concise   as   possible   and   remove   all   of   the   error   handling.
      </p>

        <cite>Conor</cite>
      <time>25:21</time>
      <p>
          So   what   does   this   mean?   Do   we   have   to   do   we   have   to   cancel   the   whole   scatter   conversation?
      </p>

        <cite>Bryce</cite>
      <time>25:25</time>
      <p>
          I   don&#39;t   know.   So   I   think   I   think   in   most   cases   you   will   do   a   first   pass,   anyways,   to   determine   the   size   of   the   decompressed   sequence   because   you   need   to   allocate   memory   for   it.   Like   I   I   i   I   struggle   to   imagine   a   use   case.   I   I   I   struggle   to   imagine   a   use   case   where   you   want   to   do   the   decoding,   but   where   you   don&#39;t   need   to   know   ahead   of   time   how   how   large   the   thing   is   gonna   be   when   decoded.
      </p>

        <cite>Conor</cite>
      <time>26:01</time>
      <p>
          I   mean   that&#39;s   just   a   I   mean   of   course,   but   that&#39;s   just   a   that&#39;s   just   a   reduction.
      </p>

        <cite>Bryce</cite>
      <time>26:05</time>
      <p>
          Right,   right.   But   I&#39;m   saying   if   you   have   uh   that   in   for   or   if   you&#39;re   going   to   do   that   reduction.
      </p>

        <cite>Conor</cite>
      <time>26:11</time>
      <p>
          And   also   it&#39;s   not   even   a   reduction,   it&#39;s   just   the   last   element   of   the   scan   that   you   have   to   do   on   the   right.
      </p>

        <cite>Bryce</cite>
      <time>26:15</time>
      <p>
          Right,   that   that   that&#39;s   what   that&#39;s   what   I&#39;m   getting.   That&#39;s   what   I&#39;m   that   that&#39;s   the   point   I&#39;m   getting   to   is   that   is   that   if   you   uh   if   you&#39;re   gonna   do   the   scan   anyways,   like   the   the   way   the   way   that   uh   when   I   asked   Chat   GPT,   it   did   like   a   reduce   first   so   that   it   could   allocate   the   temporary   storage,   and   then   it   did   a   scan   to   figure   out   you   know   the   the   the   where   shit&#39;s   gonna   go.   Um   and   then   it   did   a   third   pass   to   actually   move   stuff.   Um   and   three   passes   seems   like   overkill.   You   don&#39;t   need   that   first   reduce,   you   can   just   do   the   scan.   Um   but   I   think   that   this   may   be   a   case   where   you   can&#39;t   get   it   down   to   one   pass.   And   the   reason   you   can&#39;t   get   it   down   to   one   pass   is   because   I   can&#39;t   imagine   it   being   useful   to   like   be   like,   oh,   I   want   to   decode   this   thing,   and   here&#39;s   like   you   know,   a   gigabyte   of   storage   to   decode   it   into,   but   if   it&#39;s   bigger   than   that,   I   don&#39;t   care.   Although   now   that   I   say   it,   now   that   I   say   it,   if   I&#39;m   maybe,   maybe   actually   I&#39;m   wrong   about   that.   Maybe   like   if   I&#39;ve   got   like   some   some   thing,   some   image   I&#39;m   decoding   or   something,   where   like   I   want   to   decode   it   into   like   a   fixed-size   buffer   and   then   I&#39;m   gonna   write   it   to   disk,   right?   Because   like   I   don&#39;t   know   how   large   this   thing&#39;s   gonna   be   when   I   decompress   it,   but   I   want   to   like   decompress   it   in   stages   and   then   write   it   out   to   disk.   And   so   once   again,   I   I   I   shall   tilt   it   windmills   on   my   quest   to   figure   out   whether   we   can   do   this   on   a   single-pass   algorithm.   I&#39;m   almost   certain   that   there&#39;s   a   way   to   do   this   with   a   single-pass   algorithm.   However,   it   might   require   the   use   of   some   things   that   um   that   we&#39;ve   never   talked   about   before,   in   particular   a   completely   different   model   of   GPU   computing,   which   we   don&#39;t   typically   think   about,   which   I   think   may   be   required   in   this   case,   and   that   would   be   uh   a   cooperative   launch.   Um   because   if   we   have   a   bunch   of   groups   of   threads   that   are   working   on   this   decoding   problem   um   like   at   the   same   time,   we   we   either   need   to   be   able   to   have   an   unknown,   like   an   arbitrarily   growing   number   of   blocks,   like   of   threads,   right?   Like   each   block   of   thread   decodes   a   known   amount.   Okay,   maybe   okay,   all   right,   all   right,   all   right.   Let   me   let   me   I&#39;m   cooking   here.   So   when   you   launch   a   CUDA   kernel,   you   have   to   specify   how   many   blocks   you&#39;re   you&#39;re   running   with.   This   this   microphone&#39;s   a   little   bit   waterproof,   right?   I   don&#39;t   know.   Okay.
      </p>

        <cite>Conor</cite>
      <time>28:46</time>
      <p>
          It&#39;s   starting   to   rain   now,   folks.   We   might   need   to   kill   this.   And   also   too.   I   just   have   to   say,   uh,   I   don&#39;t   know   how   I&#39;m   gonna   edit   this   because   I&#39;m   pretty   sure   every   time   I   said   scatter   earlier,   what   I   should   have   been   saying   is   gather,   but   I&#39;m   not   even   confident   about   that   because   my   confidence   is   shot   because   I   totally   messed   up   the   description   of   an   algorithm.
      </p>

        <cite>Bryce</cite>
      <time>29:02</time>
      <p>
          So   get   out   well   to   yourself,   man.   We&#39;re   cooking   here.   I&#39;m   not   gonna.   So   I   can   I   can   imagine   two   different   types   of   implementations.   So   when   you   launch   a   CUDA   kernel,   you   need   to   s   like   you   need   to   specify   statically   how   many   blocks   of   threads   are   going   to   execute.   And   the   best,   there&#39;s   two   different   ways   that   we   could   approach   this   problem.   Way   number   one   is   the   way   that   we   typically   think   about   CUDA   computing,   where   each   block   of   threads.   Well,   look   at   this   isogram.   This   is   each   other.   Yes,   we&#39;re   gonna   we&#39;re   gonna   go   in   there.   Let   me   finish   my   spiel.   Each   block   of   threads   decodes   a   fixed   chunk   of   work.   Typically,   when   we&#39;re   talking   about   these   problems,   we   imagine   a   world   where   there&#39;s   a   fixed   number   of   blocks   of   threads,   um,   and   each   block   d   like   does   a   fixed   amount   of   work.   And   to   do   that,   you   need   to   be   able   to   know   how   much   work   there   is   in   total.   In   this   case,   we   don&#39;t   know   how   much   work   there   is   in   total.   However,   we   could   imagine   that   we   could   w   launch   a   kernel   that   that   where   we   assume   uh   we&#39;re   trying   to   get   undercover   or   we&#39;re   going   to   the   ice   cream   plate.   All   right,   here.
      </p>

        <cite>Conor</cite>
      <time>30:10</time>
      <p>
          We&#39;ll   do   them   both,   but   it&#39;s   it&#39;s   too   loud   now.
      </p>

        <cite>Bryce</cite>
      <time>30:13</time>
      <p>
          It&#39;s   alright.   So   we   could   imag   one   approach   I   could   imagine   would   be   to   say   we&#39;re   gonna   do   a   fixed   amount   of   work   per   block,   we&#39;re   gonna   launch   a   fixed   number   of   thread   blocks,   and   then   if   that   is   not   sufficient,   we   launch   a   second   kernel   that   continues   the   decoding.   Now   that   might   mean   that   we   end   up   like   wildly,   we   might   end   up   using   a   lot   more   compute   than   we   planned   because   maybe   the   maybe   the   decoding   takes   a   lot   less   work   than   we   planned.   Um   but   the   second   approach,   the   second   approach   is   this   cooperative   approach.   In   this   second   approach,   we   launch   a   much   smaller   number   of   uh   blocks   of   threads,   but   the   amount   of   work   that   each   block   of   thread   does   is   variable.   Uh   that   is   we   don&#39;t   know   ahead   of   time   or   how   much   work   they&#39;re   going   to   do.   They&#39;re   each   gonna   do   roughly   the   same   amount   of   work,   but   it&#39;s   gonna   be   what   what   we   sometimes   call   like   a   persistent   kernel   or   a   cooperative   kernel,   where   it&#39;s   going   to   continually,   it&#39;s   gonna   work   on   a   chunk   of   input,   it&#39;s   gonna   do   that   chunk   of   input,   and   then   it&#39;s   gonna   load   the   next   chunk   of   input   and   start   doing   that   next   chunk   of   input.   However,   to   write   that   type   of   kernel,   you   need   to   uh   be   able   to   have   all   of   the   uh   blocks   communicate   with   each   other   and   synchronize   with   each   other,   because   in   this   case,   once   you&#39;re   done   with   your   chunk   of   work,   to   be   able   to   start   in   the   next   chunk   of   work,   you   need   to   know   where   everybody   else   wrote   their   chunk   of   work,   uh,   which   would   require   you   to   do   a   scan.   Uh,   but   in   this   case,   we   would   maybe   want   to   do   a   um   uh   a   cooperative   scan.   Um   and   the   advantage   of   doing   that   is   that   we   can   do   the   cooperative   scan   at   the   same   time   that   we&#39;re   loading   the   next   chunk   of   input,   because   while   we   don&#39;t   know   where   the   next   chunk   of   output   will   go,   uh   we   know   we   can   we   can   statically   assign   where   the   next   chunk   of   input   will   come   from,   which   means   that   we   can   be   loading   it   concurrently   with   figuring   out   that   scan.   Okay.   I   think   I   may   have   lost   some   people   there,   but   uh,   we&#39;re   gonna   go   get   ice   cream.
      </p>

        <cite>Conor</cite>
      <time>32:25</time>
      <p>
          Yeah,   he   lost   me,   but   it&#39;s   hard   to   focus   after   the   devastating   mess   up.   I&#39;m   just   really   hoping   that   gather   is   it&#39;s   possible   that   everything   I   said   is   true   for   gather,   and   then   I   can   go   in,   and   every   time   I   say   scatter,   I&#39;m   just   gonna   cut   in.   I&#39;m   gonna   cut   out   scatter   and   cut   in   gather.
      </p>

        <cite>Bryce</cite>
      <time>32:42</time>
      <p>
          I   I   believe   that   the   thing   that   you   described   is   an   algorithm   within   thrust   and   cup.   Also,   you   gotta   buy,   don&#39;t   move,   but   don&#39;t   move.
      </p>

        <cite>Conor</cite>
      <time>32:54</time>
      <p>
          You   gonna   get   rid   of   this   thing   off   my   head?
      </p>

        <cite>Bryce</cite>
      <time>32:56</time>
      <p>
          No,   I&#39;m   just   gonna   take   pictures.
      </p>

        <cite>Conor</cite>
      <time>32:59</time>
      <p>
          What   is   it?
      </p>

        <cite>Bryce</cite>
      <time>33:01</time>
      <p>
          It   was   a   little   flaw,   I   think.   Don&#39;t   worry,   it&#39;s   okay.   It   wasn&#39;t   anything   scary.
      </p>

        <cite>Conor</cite>
      <time>33:05</time>
      <p>
          Alright,   folks,   hopefully   that   was   audible   because   we&#39;re   standing   next   to   a   bar   with   like   a   dance   party,   and   uh   we&#39;re   ending   this.   Goodbye   from   Copenhagen.
      </p>

        <cite>Bryce</cite>
      <time>33:13</time>
      <p>
          We&#39;re   not   done   yet.
      </p>

        <cite>Conor</cite>
      <time>33:14</time>
      <p>
          We&#39;re   not   done.   Yeah,   yeah,   we&#39;re   turning   it.   No,   we&#39;re   getting   we&#39;re   we&#39;re   getting   ice   cream,   then   we&#39;re   gonna   continue. We&#39;re   getting   ice   cream,   we&#39;re   not   continuing.   And   uh   we   will   pick   this   up   again.   That&#39;s   actually   a   good   question.   If   we&#39;re   recording   and   we   might   have   to   record   again   before   Wednesday.   We&#39;re   gonna   pick   this   up   again   in   five   minutes.   We   will   not.   We   will   not.   This   is   going   in   my   backpack,   it&#39;s   raining.   And   good   night   from   Copenhagen.   Maybe   we&#39;ll   record   next   time.   Uh   we&#39;re   not   gonna   have   the   energy   after   Monday   and   Tuesday.   This   has   become   very   ADSBI.   No,   I&#39;ll   have   energy   for   this.   For   this?   Yeah.   All   right.   You&#39;ll   hear   from   us.   Today   is   Saturday.
      </p>

        <cite>Bryce</cite>
      <time>33:48</time>
      <p>
          And   just   to   be   clear,   this   entire   problem   we&#39;ve   been   talking   about   is   essentially   GPU   decompression.
      </p>

        <cite>Conor</cite>
      <time>33:53</time>
      <p>
          Yes.   Yes.   Yes.   And   it   is,   am   I   not   correct,   it   is   a   very   interesting   algorithm.
      </p>

        <cite>Bryce</cite>
      <time>33:59</time>
      <p>
          It   is   a   very   interesting   algorithm.   Oh,   we   didn&#39;t   need   okay,   we   we   need   to   mention   the   final   thing,   which   is   why   we   were   talking   about   replicate   in   the   first   place,   which   is   because   of   array   broadcasting.   So   imagine   that   you&#39;ve   got   like   a   vector   um   and   a   matrix,   and   you   want   to   uh   like   apply   some   operation   and   like   you   want   to   uh   apply   some   element-wise   operation   like   uh   uh   uh   adding   or   uh   you   know   you&#39;re   explaining   this   incorrectly.
      </p>

        <cite>Conor</cite>
      <time>34:27</time>
      <p>
          It&#39;s   not   when   you   want   to   do   an   element-wise   operation.   Uh   it&#39;s   when   you   want   to   do   some   kind   of   binary   operation   on   a   matrix   and   a   vector.   So   the   example   that   we   were   talking   about   earlier,   uh   Ashwin,   who   we&#39;re   gonna   be   meeting   up   with   tomorrow   in   Norway,   posted   uh   internally   something   about   a   row-wise   softmax,   which   is   a   computation   and   I   don&#39;t   know,   machine   learning   stuff.
      </p>

        <cite>Bryce</cite>
      <time>34:50</time>
      <p>
          But   essentially   you&#39;re   performing   a   bunch   of   binary   the   fundamental   operation   to   flash   attention,   which   is   fundamental   to   GPU   inference,   which   pays   all   of   our   bills.
      </p>

        <cite>Conor</cite>
      <time>35:01</time>
      <p>
          It&#39;s   just   so   sad   because   they   give   it   a   name   like   softmax,   and   you&#39;re   just   like   like   all   these   things,   softmax,   relue.   It&#39;s   just   a   combination   of   a   couple   of   binary   operations.   Like   it&#39;s   nothing   fancy.
      </p>

        <cite>Bryce</cite>
      <time>35:13</time>
      <p>
          We&#39;ll   do   that.
      </p>

        <cite>Conor</cite>
      <time>35:14</time>
      <p>
          The   three   binary,   it&#39;s   three   two   binary   operations   and   a   unary   operation.   There&#39;s   max,   there&#39;s   summation,   I   guess   there&#39;s   division,   and   then   there&#39;s   also   exponentiation.   But   it&#39;s   like   you   do   those   things   in   order,   you&#39;re   done.   It&#39;s   like   it   it&#39;s   it&#39;s   so   boring.   And   like   they&#39;re   oh,   softmax.   You   hear   softmax   and   you&#39;re   like,   ooh,   like   how   complicated   that   look.   I&#39;m   just,   I&#39;m   just,   it&#39;s   anyway,   I   just   like   these   names,   like,   and   also   Relu,   like   I   can&#39;t   remember   what   Relu   is,   and   there&#39;s   a   couple   different   versions   of   it,   but   like   I&#39;m   pretty   sure   it&#39;s   just   like   one   over   a   number   or   something   like   that,   or   it&#39;s   like   capped   after.   Anyways,   I   just   like   as   someone   who   studied   Axe   Royal   Mathematics   and   I   suffered   through   actually   like   difficult   stuff,   they   give   all   these   fancy   names   and   it&#39;s   just   like   it&#39;s   just   basic   math.   It&#39;s   just   basic   math.   Anyways,   row-wise   uh   row-wise   softmax   involves   basically   needing   to   do   an   operation   where   you   calculate   the   maximum   of   each   row,   and   then   you   divide   each   of   the   values   in   the   matrix   by   the   maximum   of   the   corresponding   row.   Bryce   is   dancing   now.   And   so   that   means   is   that   if   I&#39;ve   got   a   you   know   a   matrix,   I   compute   uh   however   many   rows   uh   maximums,   and   then   I   want   to   divide   that   maximum   into   uh   each   of   the   values   in   each   of   those   rows.   So   it&#39;s   not   an   element-wise   operation,   it&#39;s   an   element-wise   operation   on   a   row-wise   basis,   which   means   like   if   I&#39;ve   got   a   three   by   three   matrix   and   three   values   for   the   rows,   I   want   to   divide   the   first   row   by   the   first   max,   the   second   row.   Anyways,   I   think   people   get   it.   The   point   being   though   is   you   can   use   replicate   to   turn   that   vector   into   a   matrix.   Uh   not   a   matrix,   but   like,   or   I   guess   basically   a   matrix   that.
      </p>

        <cite>Bryce</cite>
      <time>36:50</time>
      <p>
          And   this   is   for   anybody   who&#39;s   familiar   with   like   numpy   uh   style   broadcasting,   hopefully   we&#39;ve   not   lost   the   We   might   have   blown   out   the   gain   a   little.
      </p>

        <cite>Conor</cite>
      <time>36:59</time>
      <p>
          That   might   have   been   my   bad.
      </p>

        <cite>Bryce</cite>
      <time>37:00</time>
      <p>
          But   but   uh   for   anybody   who&#39;s   familiar   with   numpy   style   broadcasting,   where   when   you&#39;re   working   with   two   arrays   of   different   Aridi,   the   smaller   array   can   be   stretched.
      </p>

        <cite>Conor</cite>
      <time>37:10</time>
      <p>
          It&#39;s   Aridi,   not   Artie   sounds   like   Ariana   Grande&#39;s   cousin.
      </p>

        <cite>Bryce</cite>
      <time>37:14</time>
      <p>
          Alright,   we&#39;re   cooking   here.   Where   it   can   be   stretched   to   the   uh   to   the   rank   of   the   larger   um   array.   And   you   can   use   replicate   to   do   that   stretching.   Anyways,   we&#39;re   gonna   go   get   ice   cream   now,   but   that&#39;s   why   we   were   interested   in   talking   about   replicates.
      </p>

        <cite>Conor</cite>
      <time>37:29</time>
      <p>
          It&#39;s   actually   not   why   we   were   interested   in.   I   only   realized   when   I   was   trying   to   implement   the   row-wise   uh   softmax   that,   like,   oh,   replicate&#39;s   a   very   convenient   thing   if   you   don&#39;t   have   broadcasting   in   your   library   language.   It   just   making   the   music   loud.   I   had   implemented   replicate   a   month   before   because   I   was   trying   to   solve   some   problem   that   clearly   just   needed   a   replicate.   And   then   when   it   came   to   implementing,   it   was   like   literally   some   Perl   weekly   challenge   or   leak   code   problem   that   it   was   just   like,   oh,   like   clearly   what   I&#39;m   missing   here   is   replicate,   which   is   it&#39;s   just   an   APL   primitive,   and   I   I   hadn&#39;t   added   it.   And   uh   this   library   that   I&#39;ve   been   working   on,   uh   it&#39;s   it&#39;s   heavily   inspired   by   all   the   array   operations.
      </p>

        <cite>Bryce</cite>
      <time>38:05</time>
      <p>
          Uh   we   may   need   to   talk   to   the   uh   like   the   N   we   may   need   to   talk   to   some   of   like   the   like   NVJPEG   and   like   the   NVComp   people,   the   compression   library   people.   Well,   yeah,   I   mean   I   think   the   people   who   make   the   compression   library   know   about   compression,   yeah.
      </p>

        <cite>Conor</cite>
      <time>38:21</time>
      <p>
          Do   we   need   to   talk   to   them?   No.   Will   we   talk   to   them?
      </p>

        <cite>Bryce</cite>
      <time>38:24</time>
      <p>
          Maybe   I   do   believe   that   a   single   pass   algorithm   exists   here.   I   mean,   I   always   believe   a   single   pass   algorithm   exists   here,   but   alright,   Connor&#39;s   fixing   his   sweater,   his   his   tan   NVIDIA   sweater.   It&#39;s   gold.   There   is   no   world   in   which   this   is   gold.   It&#39;s   gold.   There   is   no   world   in   which   this   is   gold.   Alright,   we&#39;re   gonna   go   get   ice   cream.   And   I   am   dancing   now.   Very   poorly.   But   I   did   learn   some   dance   moves   when   I   was   in   Ethiopia.   They   taught   me   how   to   do   the   shoulder   thing.   Which   I   kind   of   remember   how   to   do.   Yeah.
      </p>

        <cite>Conor</cite>
      <time>39:08</time>
      <p>
          There   we   go,   folks.
      </p>

        <cite>Bryce</cite>
      <time>39:09</time>
      <p>
          She   fixed   the   sweater.
      </p>

        <cite>Conor</cite>
      <time>39:12</time>
      <p>
          My   only   sweater   and   my   only   shorts   that   I   brought   to   Norway   at   the   middle.   That&#39;s   true.
      </p>

        <cite>Bryce</cite>
      <time>39:17</time>
      <p>
          I   do   have   a   He   brought   shorts   to   Norway.   He&#39;s   gonna   be   cold.   Have   I   been   cold   this   whole   time?   But   we&#39;re   right   now   we&#39;re   in   Denmark,   not   Norway.   It&#39;s   gonna   be   colder   in   Norway.   I   have   been   in   Norway   in   September.   Trust   me,   it&#39;s   gonna   be   cold.
      </p>

        <cite>Conor</cite>
      <time>39:30</time>
      <p>
          I   think   we&#39;re   gonna   be   just   fine.   Was   I   slightly   underdressed   for   a   couple   of   the   restaurants   we   went   to?   It&#39;s   not   it&#39;s   not   a   it&#39;s   not   a   maybe,   it&#39;s   a   most   definitely   yes.
      </p>

        <cite>Bryce</cite>
      <time>39:39</time>
      <p>
          I   took   this   man   to   the   nicest   restaurant   in   Aarhus,   or   however   you   pronounce   it,   wearing   uh   his   Lululemon   shorts   and   uh   and   a   running   t-shirt.   Yeah.
      </p>

        <cite>Conor</cite>
      <time>39:49</time>
      <p>
          Was   it   a   running   t-shirt?   Oh   no,   I   kept   the   hoodie   on.   I   kept   the   I   kept   the   hoodie   on.   Yeah,   yeah,   yeah.   Listen,   you   know   what?   I   would   have   brought   nicer   clothes   if   I   had   thought   about   the   fact   that   Bryce   wanted   to   eat   at   fancy   places.
      </p>

        <cite>Bryce</cite>
      <time>40:02</time>
      <p>
          I   need   you   to   say   that   again   with   a   straight   face.
      </p>

        <cite>Conor</cite>
      <time>40:05</time>
      <p>
          Is   this   what   so   that   we   can   put   this   on   the   podcast?   I   don&#39;t   know   what   I&#39;m   doing   with   this,   but   uh   so   Bryce   asked.   Uh   was   it   Chat   GT   or   Gemini?
      </p>

        <cite>Bryce</cite>
      <time>40:15</time>
      <p>
          Chat   GT.
      </p>

        <cite>Conor</cite>
      <time>40:16</time>
      <p>
          Uh   for   some   humorous   names   for   scatter   and   gather   because   of   my   misunderstanding   earlier.   Uh   one   of   the   initial   unhumorous   was   scatter   2   and   gather   from,   which   I   really   like.   I   was   already   thinking   about   scatter   2,   but   anyways,   the   top   humorous   one   was   yeet   and   yoink.   And   then   Bryce   thought   that   was   hilarious,   and   that&#39;s   what   we   should   call   it.   But   my   response   was,   well,   that   doesn&#39;t   make   any   sense   because   yeet   means   to   like   delete,   to   get   rid   of,   to   toss   it.   You   know,   when   they   say   yeet   it,   it   means   to   get   rid   of   it.   And   that&#39;s   not   what   scatter&#39;s   doing.   So   semantically,   it   has   nothing   to   do   with   the   actual   semantics.
      </p>

        <cite>Bryce</cite>
      <time>40:48</time>
      <p>
          So   I   believe   you   said   specifically,   yeet   semantically   has   nothing   to   do   with   the   actual   operation.
      </p>

        <cite>Conor</cite>
      <time>40:55</time>
      <p>
          Yeah,   yeah,   something   like   that.
      </p>

        <cite>Bryce</cite>
      <time>40:57</time>
      <p>
          Oh   god,   I&#39;m   dying.   I&#39;m   dying.   I&#39;m   gonna   read   some   of   the   other   some   of   the   other   ones.
      </p>

        <cite>Conor</cite>
      <time>41:02</time>
      <p>
          Be   sure   to   check   these   show   notes   either   in   your   podcast   app   or   at   adspthepodcast.com   for   links   to   anything   we   mentioned   in   today&#39;s   episode,   as   well   as   a   link   to   a   GitHub   discussion   where   you   can   leave   thoughts,   comments,   and   questions.   Thanks   for   listening.   We   hope   you   enjoyed   and   have   a   great   day.
      </p>

        <cite>Bryce</cite>
      <time>41:15</time>
      <p>
          Low   quality,   high   quality.   That   is   the   tagline   of   our   podcast.
      </p>

        <cite>Conor</cite>
      <time>41:21</time>
      <p>
          That&#39;s   not   the   tagline.   Our   tagline   is   chaos   with   sprinkles   of   information.
      </p>