<?xml version="1.0" encoding="UTF-8"?>
<opml version="1.0">
  <head>
    <title>cmdln.net_2008-03-19</title>
    <expansionState>0,1,3,5,6,7,11,16,20,25,32,39,40,44,50,61,62,68,69,74,80,85,86,90,95,100,107,113,114,122</expansionState>
  </head>
  <body>
    <outline text="Intro" Offset="00:17">
      <outline text="RIP, Arthur C. Clarke">
        <outline text="http://www.latimes.com/news/local/la-me-clarke19mar19,0,393161.story"/>
      </outline>
    </outline>
    <outline text="Word of the Week: cyberpunk" Offset="02:14">
      <outline text="http://catb.org/jargon/html/C/cyberpunk.html"/>
    </outline>
    <outline text="Hacking 101: Parallel Computing, Programming" Offset="04:07">
      <outline text="Difference between serial and parallel">
        <outline text="Serial">
          <outline text="Each step must complete before the next"/>
          <outline text="Specific order"/>
          <outline text="Must get in the car first, then fill the tank at the station, then run errands"/>
        </outline>
        <outline text="Parallel">
          <outline text="Order independent"/>
          <outline text="If you have enough resources, can do at the same time"/>
          <outline text="Can shop at stores in any order"/>
          <outline text="Can divide the list with a friend, do errands in half the time"/>
        </outline>
      </outline>
      <outline text="Both old concepts with computers">
        <outline text="Applies to serial, parallel ports"/>
        <outline text="Describe how data is sent on the connected cable"/>
        <outline text="Of necessity, some pieces of low level computing are parallel"/>
      </outline>
      <outline text="The CPU itself has been traditionally serial">
        <outline text="Up through the 80s and 90s, CPUs simply ran faster"/>
        <outline text="Governed by a clock, can do only so many things each clock tick"/>
        <outline text="There are clock-less systems, uncommon, still pretty much just research"/>
        <outline text="Ticking clock helps with coordination, few parallel components"/>
      </outline>
      <outline text="Problem of frequency scaling">
        <outline text="Power consumption rises as a function of number of transistors"/>
        <outline text="Also as frequency of clock"/>
        <outline text="Moore's law driven by number of transistors per chip increasing"/>
        <outline text="Plateau in clock speeds, but more transistors"/>
        <outline text="Do more work per tick"/>
        <outline text="This is what multiple core computing does"/>
      </outline>
      <outline text="Good overview of parallel computing">
        <outline text="http://en.wikipedia.org/wiki/Parallel_computing"/>
        <outline text="Identifies problems"/>
        <outline text="Speed up is limited by slowest purely serial task"/>
        <outline text="Amdahl's Law, Gustafson's law"/>
        <outline text="Also, there is some non-obvious scaling"/>
        <outline text="A huge multiple improvement for smaller independent part beaten by modest multiple for much larger independent part"/>
      </outline>
      <outline text="Parallel programming predates multiple core">
        <outline text="Had multiple CPUs, symmetric multiprocessing">
          <outline text="More than one separate CPU per motherboard"/>
          <outline text="Uncommon but been around for some time"/>
          <outline text="Usually requires special motherboard, special operating systems code"/>
        </outline>
        <outline text="Clusters, distributed">
          <outline text="Parallel scaled way up"/>
          <outline text="Problems with interconnects, data sharing"/>
          <outline text="Do you use standard networking?"/>
          <outline text="Custom hardware?"/>
        </outline>
        <outline text="Multiple cores pushes those down to a single component"/>
      </outline>
      <outline text="Multi threading">
        <outline text="Even with only one processor, cheats to make it appear like multiple tasks run at the same time"/>
        <outline text="Takes advantage of processor running far faster than we perceive"/>
        <outline text="Switches between tasks many times per second"/>
        <outline text="Looks like each task runs independently"/>
        <outline text="Each task is associated with a thread of execution, may also be called processes but same idea"/>
        <outline text="Only one thread can be running, others are suspended but don't know it"/>
        <outline text="Think of the first time you used Windows"/>
        <outline text="Hints at problems that will get worse with multiple cores"/>
        <outline text="Order of operations cannot be just random"/>
        <outline text="Tasks that share resources have to be coordinated by the operating system"/>
      </outline>
      <outline text="Challenges">
        <outline text="Data dependency">
          <outline text="The input to task B is the output of task A"/>
          <outline text="That makes task A  dependent on task B"/>
          <outline text="Limits parallel execution, task B has to wait"/>
          <outline text="Longest chain of dependent task is known as critical path"/>
          <outline text="Whole program cannot run faster than critical path"/>
        </outline>
        <outline text="Race conditions, mutual exclusion">
          <outline text="Race condition is when one thread interferes with the expected state in another thread">
            <outline text="Each of multiple threads does the same thing"/>
            <outline text="Read a variable, increment that variable, write the new value"/>
            <outline text="For multiple threads, final value of the variable may be unpredictable"/>
            <outline text="Some threads read after others have written, some read the same value"/>
          </outline>
          <outline text="Mutual exclusion is a way of preventing threads from interfering">
            <outline text="Simplest example, associate a lock, or monitor, with a variable"/>
            <outline text="A thread must get the lock"/>
            <outline text="Only the thread that has the lock can alter the variable"/>
            <outline text="All other threads will wait, or block, until the lock becomes available"/>
          </outline>
          <outline text="Many different kinds of locks, outside the scope of this discussion"/>
          <outline text="Can still get into trouble">
            <outline text="Dining philosophers problem"/>
            <outline text="Each philosopher must get the chopsticks to either side at a roundtable"/>
            <outline text="Eventually, all diners will be blocked waiting on someone else, and so one"/>
            <outline text="Referred to as a deadlock"/>
          </outline>
        </outline>
      </outline>
      <outline text="Software approaches based on different memory models">
        <outline text="Shared memory">
          <outline text="All the threads access the same memory"/>
          <outline text="Multiple core systems are shared memory"/>
          <outline text="Have to deal with race conditions, mutual exclusion directly"/>
        </outline>
        <outline text="Distributed memory">
          <outline text="Each thread has its own memory, separate from all other threads"/>
          <outline text="How do you coordinate work?"/>
          <outline text="Threads pass messages to each other"/>
          <outline text="Clusters, grids do this of necessity"/>
        </outline>
        <outline text="Ultimate goal is automatic parallelization">
          <outline text="What if your compiler could handle locking bits of memory?"/>
          <outline text="Would have to be able to model out all the thread interactions"/>
          <outline text="Non-trivial problem"/>
          <outline text="Would save programmers having to understand, all programs would benefit"/>
        </outline>
      </outline>
      <outline text="With multiple cores on the rise">
        <outline text="More programmers need to be aware of multi threaded"/>
        <outline text="If keep programs single threaded, won't benefit since clock frequencies have stabilized"/>
        <outline text="Program will be relegated to a single core"/>
        <outline text="Thinking in threads is difficult, harder to predict what will happen at what time"/>
        <outline text="Naive assumptions can lead to disastrous results"/>
        <outline text="No easy answers, this is an active area of research, still"/>
        <outline text="For example, Java has had threading all along">
          <outline text="Still got some huge improvements, very recently"/>
          <outline text="Based on work of Doug Lea at Oswego, others"/>
        </outline>
        <outline text="2 and 4 cores are common, now"/>
        <outline text="Like frequency scaling, we'll just keep getting more cores"/>
        <outline text="Desire for automatic parallelization tools will only grow"/>
      </outline>
    </outline>
    <outline text="Outro" Offset="26:29">
      <outline text="Contact me">
        <outline text="Email to feedback@thecommandline.net"/>
        <outline text="Web site at http://thecommandline.net/"/>
        <outline text="IM to command.line@skype"/>
        <outline text="Listener comment line is 240-949-2638"/>
        <outline text="del.icio.us tag is &quot;for:cmdln&quot;"/>
        <outline text="http://twitter.com/cmdln"/>
      </outline>
      <outline text="I'd like to thank libsyn.com for AAC hosting and Wouter de Bie for MP3 hosting"/>
      <outline text="These notes and the show audio and music are covered by a Creative Commons license">
        <outline text="http://creativecommons.org/licenses/by-nc-sa/3.0/us/"/>
        <outline text="Attribution, non-commercial, share alike"/>
      </outline>
    </outline>
  </body>
</opml>
