This work is licensed under a
Creative Commons License.
|
Friday, May 09, 2008
Teaching Parallelism
Posted by Lance
Uzi Vishkin wrote these ideas on how to teach a parallel computing course as a comment on my earlier parallelism post.The basic claim is that:
I expect theorists to endorse this argument and use it to convince their colleagues that PRAM algorithms need to be taught. But, I have to be frank. I am concerned that some of us will do the following: teach a course on parallel algorithms as a purely theory course WITHOUT any connection to programming. This will miss the point as it ignores the need to relate algorithms to programming. The Q&A at the end of this text elaborate further on the programming issue.
- It does not make sense to have a new platform of general-purpose parallel computing succeed the established serial platform without having a one-to-one match of EVERYTHING, including algorithms and data structures.
- In particular, it does not make sense to teach parallel programming without teaching parallel algorithms and data structures. The gap between programming and algorithms must be bridged, so that the continuum from algorithms and data-structures to programming will resemble as much as possible the continuum in serial computing.
- Since the PRAM theory is the only serious candidate developed in nearly 3 decades of research, PRAM algorithms have got to be taught.
As others have implied, you can find several fine sources for PRAM algorithms. For this reason, my comments below mostly focus on a way to address the parallel programming issue:
Finally, please note that this type of programming cannot be too difficult. I have given a 1-day parallel algorithms tutorial to a dozen high school students in Fall 2007 and subsequently some of them managed to do on their own 8 programming assignments. In fact, the above link to programming assignments gives these 8 programming assignments. The only help the high school student got was one office hour per week by an undergraduate teaching assistant. They did not get any school credit for their work. Their participation was in the context of a computer club after completing their regular school work (8 periods per day).
- In class presentation.
- Read Section 2.1 entitled XMTC in FPGA-Based Prototype of a PRAM-On-Chip Processor. It reviews a modest extension to the C programming language called XMTC that allows PRAM-like programming. XMTC essentially adds only 2 basic commands to C: Spawn and PS (for prefix-sum).
- Devote a total of around 15-20 minutes similar to slides 37-39 in these slides to present XMTC. Slide 40 can guide a discussion.
- Supporting documentation. The students should then be referred to: the XMTC Manual and the XMTC tutorial.
- Programming assignments. Please look up under assignments on this course page.
- Running programming assignments. The UMD PRAM-On-Chip project is on track for public release by the end of June 2008 of:
The will allow your students to run XMTC code on an emulated 64-processor PRAM-On-Chip machine. To remind you, a hardware prototype of such a machine (using FPGA technology) has been in use at UMD since January 2007. A compiler that translates XMTC to OpenMP will also be released, giving your students an alternative way to run their assignments.
- a cycle accurate simulator of the PRAM-On-Chip machine, and
- a compiler from XMTC to that machine.
If you are looking for code examples, you are welcome to write to me.
Here are some Q&A:
Q: I never learned parallel programming formally, but I picked up some ideas in my free time from Java/MPI/OpenMP/etc. How do any of these relate to XMTC parallel programming?
A: XMTC parallel programming is simpler and different.
Q: The problem of algorithms being taught independently of programming is present within the exclusively serial world. What would you say to the many theorists who are resistant to the idea of having a heavy programming component in their courses?
A: IMHO the serial case is completely different. Most students have experienced/learned serial programming BEFORE taking the serial algorithms course. This is NOT the case for parallel programming. My experience is that students learn best if parallel programming is coupled with parallel algorithms. The main difference is that the parallel algorithms course is where parallel programming should be FIRST taught. The reason is that parallelism requires introduction of some first principles representing an "alien culture" to students. In contrast, serial computing is related to: (i) mathematical induction, (ii) the way our brain instructs our body (as a single processor), etc. There is nothing out there that prepares us for parallel computing.
Q: What text do you use for teaching parallel algorithms?
A: I have been using my class notes.
Warm thanks to Adam Smith and Aravind Srinivasan for their helpful comments on an earlier draft of this text.
5:29 AM #
Thursday, May 08, 2008
Electronic Commerce and Prediction Markets
Posted by Lance
Registration has opened for the upcoming ACM Electronic Commerce Conference (which I am general chair) in Chicago July 10-12. The conference is immediately followed by AAAI and The Third World Congress of the Game Theory Society both also in the Chicago area. Before the EC conference is a series of workshops and tutorials covering topics from on-line advertising to social networks.One of those workshops covers an area that has excited me for several years now, The Third Workshop on Prediction Markets. Prediction markets aggregate information quite efficiently in ways we don't yet fully understand and remains a fertile area of study. Legal limitations on betting have restricted the applications of prediction markets, particularly in the US, but that might change soon. The Commodity Futures Trading Commission (CFTC) is asking for public comment for regulations of prediction markets. Their concept release gives a nice discussion of the legal issues. Will this lead to more legitimate real money markets in the US? Time will tell.
9:55 AM #
Wednesday, May 07, 2008
Any Questions?
Posted by Lance
A speaker in a seminar talk loves to get questions during the talk for this means that at least one person is trying to follow the talk. A talk with no questions means everyone is either completely following the talk or is completely lost, most likely the latter.Each question though involves three parties: the questioner, the speaker and the rest of the audience. A good talk has a certain rhythm and questions can disturb that rhythm. So how does the audience feel about the questions? Depends on the question.
At the end of the talk the questions usually suggest various extensions to the work that can often go on forever. Most of the audience just wants to escape but is too polite to leave. The host again needs to end the discussion. Having food in another room to continue the discussions in can help immensely.
- Questions that clarify the model or some aspect of the proof. We need these questions to properly follow the talk. When others ask these questions, I learn that I really hadn't understood the model when I had thought I had.
- Questions that argue against the model or results. Usually entertaing but can often degenerate into a long argument. The host needs to become a moderator and has to give one of those one-time nerd jokes that have become standard lexicon: "Take this discussion off-line."
- Questions that point out mistakes. Usually annoying and serves no purpose unless, of course, it takes down the whole proof.
- Questions that prove how smart the questioner is. The most annoying. I cringe whenever I hear a question starting with the word "So".
9:15 AM #
Tuesday, May 06, 2008
Vanished from the web- of more interest...
Posted by GASARCH
In my last post I told of a Masters Thesis that vanished from the web, into the night. I suspect I am one of the few people who wants a copy, hence this incident will not attract any wider attention. This is a contrast to today's tale of vanishing.
A while back a talented fellow named Kevin Ryan recorded and put on the web Dylan hear a who, which was 7 Dr. Suess stories sung in Dylan style. (Since I own what is probably the largest collection of Bob Dylan satires in the world-- 127 satires and an additional 14 songs that I don't count as satires but others do--- this was a must have.)
Kevin Ryan got a Cease-and-desist order from the Dr. Suess people to remove it, and he did, as you can see here. One version of the story, which seems correct, is in this article
One Moral of the story: If you find a SOMETHING on line that you may want to keep, DOWNLOAD IT. Do NOT depend on it still being there later. But there is a different issue here:
Is what the Dr. Suess people did legal? I do not know. Is what the Dr. Suess people did moral? I do not know. Is what the Dr. Suess people did stupid and against their own interests? Yes. I can picture someone hearing Dylan hears a who and going out and getting some Dr. Suess books. I cannot picture hearing it and therefore not getting some books. Businesses need to devolp different business models for the e-world in which we live. For example, they may have worked out a deal where a link to purchase Dr. Suess books is on that same website and/or an advertisement. It is likely there are other possiblities. For more on this, read the book wikinomics, which I might blog about at some later date.11:38 AM #
Monday, May 05, 2008
If you find something online download it NOW
Posted by GASARCH
A few months ago I was looking into some of the origins of Ramsey Theory (in particular I was looking at what Hilbert needed Hilberts Cube Lemma for) and I came across the following onlineCombinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman by Yudi Setyaan. A Thesis submitted in partial fulfillment of the requirements of the defense of Master of Science in the Department of Mathematics and Statistics. Simon Fraser University, July 1998I printed it out and still have it. It was not helpful for what I wanted, but it was interesting and I'm glad to have it.
Recently I wanted to email it to someone else so I searched for it again. Its gone! Now you have to pay for it at amazon. I also looked for the author on line to see if he might email me a copy (I doubt he gets any money from it and I suspect he would be delighted to find out the someone actually read it.) Couldn't find the authors email address, though I am hopeful that I will.
Moral of the story: If you find a document on line that you may want to keep, DOWNLOAD IT. Do NOT depend on it still being there later.9:18 AM #
Friday, May 02, 2008
Report on Sym for Lipton's 60th bday (guest post Ken Regan)
Posted by GASARCH
(Guest Post by Ken Regan)
A two-day symposium in honor of Richard J. Lipton's 60th brithday was held April 27--28 in the brilliant new Klaus Advanced Computing Center at Georgia Tech. The wide variety of talks influenced by Dick Lipton's ideas attested his ability to say something deep about many subjects. Deep and still keeping to a dictum of Hilbert featured on one speaker's slides: the simple attracts. An example referenced in many talks was his ("one-paragraph") proof of the self-reducibility of the permanent Wikipedia entry). Another referenced his co-authorship of a March 2008 report to the Georgia Secretary of State with recommendations and advisories on electronic voting.The first talk by Richard Karp carried the message that problems of the Hitting-Set kind are easier most often in practice than their worst-case NP-complete pedigree leads one to expect. This was supplemented by Neal Young's second-day talk involving Lipton's question, "Is it hard to generate random hard instances of NP-complete problems?" Ravi Kannan spoke on the practicality of finding good approximate equilibria for non-zero-sum games and market situations. Dan Boneh showed the extent to which even certified-sound cryptosystems become vulnerable when keys k are used to encrypt data that overtly contains k, or when there are closed cycles of encodings of multiple keys. He also explained how Lipton's kung-fu wielding of the Chinese Remainder Theorem in attacks on RSA and kin slowed web servers by 8%. Anita Jones surveyed the urban landscape of computer security, and propounded the sequence of system calls made by a program as a signature by which to identify malware.
Michael Rabin described a practical implementation of zero-knowledge protocols for high-stakes auctions, one point being efficiency gains from coding on the arithmetic rather than going all the way down to Yao's oblivious ZK circuit verification. Nisheeth Vishnoi presented a polynomial-time algorithm that distinguishes the "Yes" case of the "Unique Games Conjecture" from a tighter "No" case asserting also that the underlying graph is an expander (paper). This evinces a surprising difference between "Unique Games" and non-unique Constraint Satisfaction Problems, and suggests that if the UGC holds at all, any proof must differ widely from traditional proofs establishing hardness of CSPs.
Erik Winfree's multimedia talk "Is DNA Computing?" demonstrated that whatever one feels about the feasibility of large-scale DNA computers (on which Lipton followed Adleman's first paper with a neater formulation), DNA activity is undeniably computational.
Giovanni diCrescenzo talked on Lipton's idea of storing keys not as small files but parceled among huge hunks of stored data, so that intrusion attempts to recover them leave huge footprints, applying hashing and extractors to implement it. I surveyed the frontiers of super-linear lower bounds, including the Lipton-Tarjan separator theorem's relevance and Dick's part in time-space tradeoffs for SAT, and used Allender-Koucky's observation as a segue to super-polynomial lower bounds. I outlined my position that "Very High Degree" methods are capable of surmounting known barriers and may be necessary.
Dick's longtime friend and associate Richard DeMillo surveyed Lipton's contributions to fundamental problems of software correctness. Wenke Lee focused on how 'bots have opposite behavior and intent to viruses, and how the company Damballa founded by Merrick Furst, him, David Dagon, and Lipton combats botnets.
Parikshit Gopalan presented new ideas on the lower bound frontier of ACC[m] for composite m, and continued a running gag on the power of Chinese remaindering. But Avi Wigderson planted a Monty Python foot on further progress by demonstrating that almost all known complexity-class results preserve themselves under an arithmetical form of relativization, while P vs. NP and most other frontier relations do not. Memo to new graduate students honing their technical abilities by building oracles A separating classes C from D: the ante just got upped to building both A and a low-degree extension A' such that C^A is not contained in D^{A'}, so then proving C contained in D would require "non-algebrizing techniques". And various vice-versas...all of which tighten the rules of equation-solving needed to build A. One sentence of hope remained on Avi's slides actually by Scott Aaronson: methods that go beyond treating (feasibly-constructed) multilinear extensions as black-boxes can possibly evade the new barrier. Jin-Yi Cai closed by presenting a "Holographic" algorithm toolkit of subversive power, whose steep learning curve is helped by its affinity with quantum computation.
On the learning-curve subject, I came away with the impression that although it is often higher for cryptographic protocols than algorithms, more of the former actually get implemented. Of course, Karp has always stood for implementing algorithms, and Neal Young reported on how his beats simplex for its target domain, but I'm just reporting my positive impressions of security applications from the two days. In all it was a rich meeting, with "not too many embarrassing stories" for Dick and lots of energy.
10:05 AM #
Thursday, May 01, 2008
The ID Conundrum
Posted by Lance
I called human resources at Northwestern with a question about health insurance. After she had trouble tracking me in the system we discovered Northwestern had the wrong social security number for me. Northwestern take great care to hide my SSN, using an employee number on my Faculty ID card and allowing me electronic access to my paycheck with nary a social security number in site. Northwestern would probably not use my SSN at all except they need it to report taxes which would have caused all sorts of havoc had, by pure luck, I didn't catch the mistake.That's the problem with the social security number. We've become so scared of using the SSN, the number has become useless. What we need is a unique public ID that we are not afraid of using. In my ideal world, we would all have a public and private ID. With someone's public ID I could use it to call them, text them, IM them, email them even send them postal mail by simply writing their ID number on the envelope and the post office's computers will know how to route the mail. People would use their private ID to log onto some central server to set the places that the public ID points to as well as block certain users and deal with privacy restrictions.
You could use your public and private ID to log onto all your services so you don't need to keep separate accounts on various webpages. Both Northwestern and the University of Chicago have single electronic IDs and passwords to access email, benefits and wage information, course information, get wifi access and much more.
Now that people avoid using the SSN as a public ID, cell phone numbers and email addresses are beginning to play that role. Privacy advocates have slowed down efforts to have a public ID for a variety of reasons. But the great need for an ID means the market will start using whatever it has available and isn't it better to carefully design a proper public/private ID than have some ad-hoc market-driven system instead.
10:50 AM #
Wednesday, April 30, 2008
AAAC in Hong Kong
Posted by Lance
I just came back from an all too short trip to Hong Kong for the first annual meeting of the new Asian Association for Algorithms and Computation. The AAAC would like to become the Asian version of SIGACT and EATCS. The conference was a good start but dominated by the Japanese and needs in future to draw researchers from across Asia. I went as a speaker, but also as a supporter as I would love to see theory grow around the world and while East Asia has produced a few great researchers, it has not even come close to reaching its potential.This was my first trip to Hong Kong and the three dimensionality of central Hong Kong is quite striking with many tall buildings built on various points on a hill and in some cases seemingly on top of other buildings. To get from my hotel to the conference at Hong Kong University, I took a series of outdoor escalators, crossed a bridge and then an elevator followed by some stairs. You need to keep track of elevation to get around that city.
I had never been to China. Did this trip to Hong Kong count? Technically yes, since 1997 Hong Kong is officially a Special Administrative Region of China and shares much of the culture and cuisine of China. But a different currency, visa requirements and economic structure makes it seem like a separate country. Someday I will get to mainland China and make this point moot.
12:15 PM #
Archives
