Slide 1Finding AliensFinding the AliensProcessing SignalsFinding the Aliens CheaperPublic Distributed ComputingBOINC (Seti@Home) ClientBOINC ManagerIncentives are NecessaryIncentives are DangerousPreventing CheatersWhy is finding aliens so “easy”?“Harder” TaskScheduling MeetingsPartial Ordering of EventsRace ConditionPreventing Race ConditionsLockingDeadlocksWhy multiple processors is hard?ChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 37:How to Find Aliens (and Factors)2CS150 Fall 2005: Lecture 37: Finding AliensFinding AliensArecibo Antenna, Puerto RicoFrom http://www.adl.gatech.edu/research/tff/ph1final_radio.html3CS150 Fall 2005: Lecture 37: Finding AliensFinding the Aliensfor signal in signals: power = findPowerSpectrum (signal) if (isAlien (power)): print “Found an alien!” + signal4CS150 Fall 2005: Lecture 37: Finding AliensProcessing Signals•Power spectrum•Find patterns in signal•Eliminate natural and human-made signals•Today: –BlueGene, 280Tflops/s~$200 per Gigaflop•No success finding aliensCray T3E-1200E (~1998)1 Teraflop/s = Trillion floating point operations/sec5CS150 Fall 2005: Lecture 37: Finding AliensFinding the Aliens Cheaperparfor signal in signals: power = findPowerSpectrum (signal) if (isAlien (power)): print “Found an alien!” + signal Note: python does not actually have parfor, but other languages do.Parallel for: instead of doing each element sequentially in order,we can do each element in parallel on a different machine.6CS150 Fall 2005: Lecture 37: Finding AliensPublic Distributed ComputingCentralServer(setiathome.berkeley.edu)InternetMillions of home PCs7CS150 Fall 2005: Lecture 37: Finding AliensBOINC (Seti@Home) Client8CS150 Fall 2005: Lecture 37: Finding AliensBOINC Manager9CS150 Fall 2005: Lecture 37: Finding AliensIncentives are Necessary10CS150 Fall 2005: Lecture 37: Finding AliensIncentives are Dangerous•People will cheat*•How to cheat?–Respond with the “there are no aliens” message without actually doing all the work•Chances of getting caught?–0 (Assumes all jobs have no aliens. So far this is true.)* Only applies in real world, not at UVa.11CS150 Fall 2005: Lecture 37: Finding AliensPreventing Cheaters•Send the same job to multiple workers–Wastes computing–What if the cheater controls many machines?•Instead of response being “no aliens” make clients send a response that proves they did computation•Sometimes send out fake jobs that have aliens in them–Clients must find the fake aliens–Need to make sure the fake jobs look just like real jobs–(Airport security scanners work like this also)Doug Szajda and colleagues at University of Richmond work on these problems (see link on notes)12CS150 Fall 2005: Lecture 37: Finding AliensWhy is finding aliens so “easy”?•Can be broken into many tasks•Each task can be done completely independently–No shared memory between the tasks•The data to describe a task and response is small compared to the computing–SETI@home jobs are 350KB data download, 1KB upload, 3.9 Trillion operations (several hours on PC)Note: we haven’t yet found any aliens, butits easy to set up the computation...13CS150 Fall 2005: Lecture 37: Finding Aliens“Harder” Task•Dividing your PS8 project work among your teamPS8 Update: you have 1 week left!If you do not have basic functionality working by tomorrow, arrange to meet with me14CS150 Fall 2005: Lecture 37: Finding AliensScheduling MeetingsAlice wants to schedule a meeting with Bob and ColleenBob Alice Colleen“When can you meet Friday?”“When can you meet Friday?”“11am or 3pm”“9am or 11am”“Let’s meet at 11am”“Let’s meet at 11am”Reserves 11amfor meetingReserves 11amfor meetingPicks meeting time15CS150 Fall 2005: Lecture 37: Finding AliensPartial Ordering of Events•Sequential programs give use a total ordering of events: everything happens in a determined order•Concurrency gives us a partial ordering of events: we know some things happen before other things, but not total orderAlice asks to schedule meeting before Bob repliesAlice asks to schedule meeting before Colleen repliesBob and Colleen both reply before Alice picks meeting timeAlice picks meeting time before Bob reserves time on calendar16CS150 Fall 2005: Lecture 37: Finding AliensRace ConditionBob Alice Colleen“When can you meet Friday?”“When can you meet Friday?”“9, 11am or 3pm”“9am or 11am”“Let’s meet at 11am”“Let’s meet at 11am”Picks meeting timeDoug“When can you meet Friday?”“9, 11am or 3pm”“Let’s meet at 11am”Reserves 11amfor Doug“I’m busy then…”17CS150 Fall 2005: Lecture 37: Finding AliensPreventing Race Conditions•Use locks to impose ordering constraints•After responding to Alice, Bob reserves all the times in his response until he hears back (and then frees the other times)18CS150 Fall 2005: Lecture 37: Finding AliensLockingBob Alice Colleen“When can you meet Friday?”“When can you meet Friday?”“9, 11am or 3pm”“9am or 11am”“Let’s meet at 11am”“Let’s meet at 11am”Picks meeting timeDoug“When can you meet Friday?”“3pm”“Let’s meet at 3”Locks calendar19CS150 Fall 2005: Lecture 37: Finding AliensDeadlocksBob Alice Colleen“When can you meet Friday?”“When can you meet Friday?”“9, 11am or 3pm”Doug“When can you meet Friday?”Locks calendarfor Alice, can’t respond to Doug“When can you meet Friday?”Locks calendarfor Doug, can’t respond to AliceCan’t schedulemeeting, noresponse fromBobCan’t schedulemeeting, noresponse fromColleen20CS150 Fall 2005: Lecture 37: Finding AliensWhy multiple processors is hard?•Too few ordering constraints: race conditions•Too many ordering constraints: deadlocks•Hard/impossible to reason modularly–If an object is accessible to multiple threads, need to think about what any of those threads could do at any time!Worry: nearly all standard desktop computers will be multi-processors soon!21CS150 Fall 2005: Lecture 37: Finding AliensCharge•The easiest way to solve distributed scheduling problems is to “undistribute” them:–Find your teammates now and make sure you know what you are doing next week•Wednesday: Google–Read the paper distributed today•Friday: Review–Send me your questions and topic requests•Monday: PS8