Log in

No account? Create an account

Previous Entry | Next Entry

Parallel Programming: Announcement

As some of you know, I have been working on a book on parallel programming. My thought had been to complete it, then announce it. But I finally realized that it really never will be complete, at least not as long as people keep coming up with new parallel-programming ideas, which I most definitely hope will continue for a very long time.

So, here it is!


Gautham Shenoy
Jan. 3rd, 2011 09:37 am (UTC)
Wow this is brilliant!

I do remember you giving Swathi/me a link to the book you were working on (perfbook.git IIRC) when she wanted to use RCU for DNS related work! This is the same book, right ?!
Jan. 4th, 2011 06:53 am (UTC)
Yep, same book, later version. ;-)
Jan. 3rd, 2011 11:24 am (UTC)
wow - thanks!
Holy crap, this is great! Just skimming it now. I learned a lot from reading the linux kernel docs, but this book is way better. Hopefully more people take a crack at this stuff.
Jan. 3rd, 2011 11:48 am (UTC)
Wow... This is great. I guess this means you don't have any concrete plans for physical publication, right?
Jan. 3rd, 2011 11:54 am (UTC)
Because nobody has ever published a successful technical book and also made it available on the Internet? :)
Jan. 3rd, 2011 06:58 pm (UTC)
Physical publication
I've had pretty good luck putting PDF's up on lulu.com; there is $0 fixed cost to the author (though you need to make a PDF with embedded fonts for the document, and an image file for your cover) and the paperback books have been fairly sturdy (i.e., in reasonably good condition after a year or more of being left out as a "reference copy" in our CS teaching lab).

Based on a quick look at this book, I'd probably pick up a paper copy if a high-quality one was easily available: I still haven't adopted an e-reader, and I hate trying to collect 100+ page documents off the printer. (Note that I have no financial interest in lulu.com or its competitors.)

Jan. 3rd, 2011 01:44 pm (UTC)
Thanks Paul
Great work Paul, and everyone else who put time into this wonderful book! Very much appreciated.
Jan. 3rd, 2011 07:27 pm (UTC)
Flow-Based Programming

I'm working on a flow-based programming system in which cooperating components are the "IC/Integrated Circuit" of it's parallel programming model. The components are modeled as cooperating co-routines/green threads/fibers which read and write to each others I/O channels.

In the simplest implementation there are no actual contention, locking or critical code sections because each component reads from it's inputs, performs some computation and writes to it's outputs. After the component is done it yields the CPU to the scheduler which transfers control to the next component.

In actual practice, the cooperative components are distributed between amongst 'n' available threads, with one thread per CPU core. Data transfer between components running concurrently on separate threads is is passed through non-locking, cache-coherent, FIFOs.

This system has the advantages of simplicity and re-usability of programming (much like UNIX pipes) with relative freedom from cache stalls and the thread rescheduling that happens when a locked critical section is encountered by a thread.

My system is, of course, nothing new. Systems like LINDA started flow-based programming a long time ago.

I was wondering if you were going to be covering flow-based systems within your analysis (Obvious MPI approaches this using message passing).



Jan. 4th, 2011 08:52 pm (UTC)
Re: Flow-Based Programming
Hello, Eris,

The closest thing to this approach currently in the book is pipelining, which is a trivial variant of flow-based programming. I don't have any immediate plans to go beyond this at the moment,

Were you interested in writing up a survey of the various flow-based programming efforts, with emphasis on open-source software?

Thanx, Paul
Jan. 10th, 2011 01:53 am (UTC)
Re: Flow-Based Programming
I also would like to see a section on Flow-Based Programming (FBP) in your book, or at least a link to my web site - http://www.jpaulmorrison.com/fbp . FBP started within IBM, and was used for the batch part of a major banking project in the '70s. IBM had a couple of FBP projects, but eventually dropped the last one around 1992. Since then, however, it has now spread world-wide, and IMHO a book on parallel programming is not really complete without a description of FBP. BTW the 2nd edition of my book on FBP came out in May of last year. Feel free to contact me if you need more info.
Regards, Paul Morrison
Jan. 3rd, 2011 07:33 pm (UTC)
Thank you very much for this great book!
Jan. 4th, 2011 03:36 am (UTC)
On the subject of Moore's Law
I'm reading the book now, and I feel the need to state that you rather thoroughly misapply Moore's law on page 15. Moore's Law has exactly nothing to do with either MIPS or clock speed except in the most roundabout way possible. It merely states that:

Transistor count per unit area per unit money will approximately double every 18 months.

Thus, your chart in no way substantiates the statement that Moore's Law has ceased to provide benefit. Pure MIPS might have been slightly more useful than the mixed MIPS/clock rate chart you present, seeing as the Core line of CPUs has lower clock speed than the Pentium 4 series almost across the board, but is far more powerful. Still, Moore's law is the very thing that has made multicore possible - aside from dedicating more transistors to a single core to make it faster, chipmakers have enough to dedicate them to an entire second, fourth, or sixth core.
Jan. 4th, 2011 08:55 pm (UTC)
Re: On the subject of Moore's Law
The wording on page 15 is "ceased to provide its traditional benefit" rather than "ceased to provide benefit". For a long time, the benefits of Moore's Law included frequency increases due to transistor scaling, and those traditional frequency increases are no longer happening.

That said, I can see how you might read the current wording in that way. I am considering adding a Quick Quiz raising your point. Does that seem reasonable to you?
Jan. 6th, 2011 04:47 am (UTC)
Re: On the subject of Moore's Law
Yes, that would help a great deal. On a different note, how would you prefer to be given spelling and grammar corrections? For instance, in the preface you say "You [sic] mission, if you choose to accept..." Not only should the 'You' be 'Your', but that idiom is typically phrased as "Your mission, should you choose to accept it...". Also, on page 14 you typo'd Steven Hawking's last name, putting a superfluous 's' at the end.
Jan. 4th, 2011 04:08 am (UTC)
HTML version?
Any chance of also outputting an HTML version?

I'm not a fan of PDF; it's (generally) not reflowable.
Jan. 4th, 2011 08:58 pm (UTC)
Re: HTML version?
No immediate plans. That said, I would welcome a good patch that did this.

The challenges will be handling the Quick Quizzes and the other script-extracted content. It might be possible to provide scripting that fixed things up for latex2html, but I have not put much thought into this.

Again, I would welcome a good patch that did this.
Jan. 4th, 2011 09:50 pm (UTC)
Re: HTML version?
It's now on my list of things to do…

A quick look brings up pandoc, which can convert a subset of LaTeX to HTML as well as ePub (useful for all those folks with electronic readers, e.g. Nook, iPad).
Jan. 5th, 2011 07:09 pm (UTC)
Re: HTML version?
Thank you, I have added pandoc to my todo.txt list.
Jan. 6th, 2011 01:55 am (UTC)
Re: HTML version?
I created a HTML version by naively executing latex2html. It probably has some missing parts and it gave a number of warnings. I then used calibre to generate epub and mobi formats. I will read the mobi format on my Kindle.

I don't have the time to check that the formatting works, but here's the result for anyone else as impatient as I am :-)


Jan. 6th, 2011 06:17 am (UTC)
Re: HTML version?
Many thanks, Paul!!! I have added these links to my perfbook web page.
Jan. 4th, 2011 01:12 pm (UTC)
typo in perfbook
> The pthread_mutex_lock() primitive “acquires”
the specified lock, and the pthread_mutex_lock()
“releases” the specified lock.

lacks a "un" in the second pthread_mutex_lock()

Jan. 4th, 2011 05:17 pm (UTC)
Re: typo in perfbook
And the footnote 4) in paragraph 5.3.1 seems misplaced.

Jan. 4th, 2011 09:04 pm (UTC)
Re: typo in perfbook
Someone beat you to the missing "un", but you are quite right that the footnote looks a bit like an exponent. I have moved it to the end of the sentence.
Jan. 4th, 2011 04:18 pm (UTC)
Great book
Thanks for putting this together!
Let me know if there's a way to donate $ for your efforts, as a thank you. =)
Jan. 4th, 2011 09:05 pm (UTC)
Re: Great book
Thanks to all for the props!

No need for $$$, but thank you for asking.
Jan. 5th, 2011 03:15 am (UTC)
Thanks! This looks very interesting.

One typo -- on page 154, item 5 in the list should be the consumer picking up the producer's timestamp, yes?
Jan. 5th, 2011 07:20 pm (UTC)
Good catch!!! I have committed and pushed a fix into the git archive.

Thank you!
Jan. 5th, 2011 06:27 pm (UTC)
What, specifically, is the focus of the book?
Is this intended to be an introduction to parallel programming as a concept (using POSIX as an illustration), or more of an introduction to parallel programming as a practical endeavour?

If the former, there's really not a whole lot that needs to be added to the book. It's very clearly written and covers most of what anyone would need to understand parallelism. The only chapter I don't see is one on interconnects. This matters because interconnects define what will (and will not) work in the way of techniques. It's not that the interconnects are directly important, but they do place limits on those things that are.

On the other hand, if it's a book on practical parallel programming, you'd need a section covering the ideas in communication. "Conflicting Visions of the Future" is excellent as-is and might well be the correct place to discuss things like RDMA, but it doesn't feel right for discussing message passing versus networked inter-process communication.

I have absolutely no idea if you'd want to cover instruction-level parallelism (as per Silk and Silk++, but also an area a lot of early parallel research looked into). It's such a totally different beast than regular parallelism.

Bottom line, great book and I'd love to see if there's anything I could usefully contribute, but to avoid wasting your time or anyone else's, I'd want to know what would be interesting to you as the author-in-chief and editor-in-chief.
Jan. 5th, 2011 07:34 pm (UTC)
Re: What, specifically, is the focus of the book?
An introduction to parallel programming as a practical endeavor, with emphasis on helping people understand how to adjust the overall design of their software so as to get the most parallelism benefit for the least pain, time, and trouble.

The focus at the moment is primarily on shared memory because such systems are cheap, easy to set up, and readily available. Plus because my own experience has been primarily with shared memory, and additionally because the most likely audience are people using multi-core systems.

When you talk about interconnects, are you thinking in terms of the internal interconnects in shared-memory/multicore systems, or in terms of the message-passing interconnects used in large supercomputing clusters?

"Conflicting Visions of the Future" should be for topics where there is genuine uncertainty and conflict. Possible topics include limits to hardware and software scalability, multicore-computing fads from various groups, and what sorts of parallel-debug assists are required. That said, this book is not to be a marketing vehicle for either vendors or academia.

I of course welcome contributions! One question to ask yourself is "what area am I expert in that a lot of people need to know or will soon need to know?" Thoghts?
Jan. 5th, 2011 10:28 pm (UTC)
Re: What, specifically, is the focus of the book?
In terms of interconnects, I'm thinking busses (in the case of multicores and SMP) and ethernet (for budget message-passing clusters, MOSIX and Kerrighed users and remote calls - including RPC, CORBA and Linux' TIPC). I wish that I could include fast serial links, but the Transputer died in the 1990s and Intel's iWarp died soon after. Those are more Visions of the Past, which I consider a shame.

In other words, stuff that makes a system almost transparently scalable. Explicit high-level stuff like MPI-2 and Bulk Synchronous Processing get ugly, there's masses of tedious detail, and frankly most of the important stuff (avoiding deadlocks, avoiding simultaneous writes, etc) is stuff you already cover. Some aspects of parallelism are universal.

In the case of ethernet, for example, there's the question of how to pretend to have shared memory. (Distributed Shared Memory schemes tend to be rare and are often badly written.) There's also the question of whether you can use process migration systems like MOSIX or Kerrighed to do MIMD-style parallel processing more effectively than you could on a multi-core or SMP computer.

Also on Ethernet, you can very easily pass around a lot of data to a lot of machines simultaneously, using Scalable Reliable Multicast. Which, incidentally, MPI does not use. MPI rotates round the list of destinations in a collective call and sends messages on a sequential basis. Implementations of SRM and NORM (NACK-Oriented Reliable Multicast) are widely available for most platforms, Windows and Linux included, so it's vendor-independent. They are not, however, significantly used in the industry, although one would think that MISD-style parallelism would find the mechanism to be extremely valuable.

For many busses, the time it takes to switch a lane from one direction or target to another is absurdly high. The cost of working at such fine detail is also absurdly high, since a lot of parallel processing languages (UPC, Erlang, etc) are too high a level to let you do much tuning. The question is how to make the best use of time to get the best use out of the system. And that's a hard problem.

"What area am I expert in that a lot of people need to know or will soon need to know?" If I knew that, I'd be rich. :) I'm expert in plenty of areas, I frequently find use for that expertise, but anticipating which areas would be useful for others has always been a tough one for me.
Jan. 9th, 2011 06:49 pm (UTC)
Paul E. McKenney's Journal - Post a comment
.... here and so ... ..
Jan. 13th, 2011 10:21 am (UTC)
[Patch] send dvips output to file
When running "make", the generated DVI was sent directly to printer rather than into a .ps file. The patch at http://pastebin.com/tkA8wj6W fixed it for me.

Btw. do you know if there's a way to generate a Table of Contents in the PDF, which would be displayed in the side pane in many PDF viewers? That would be really useful for viewing such a large book.
Jan. 16th, 2011 12:01 am (UTC)
Re: [Patch] send dvips output to file
I added the "-o" flags to dvips, thank you! It might be possible to generate the table of contents in the PDF by switching to pdflatex, which might be helpful for other reasons.
Feb. 8th, 2011 08:45 pm (UTC)
Re: [Patch] send dvips output to file
Thank you for the report! All of the remaining dvips commands now have "-o". Hopefully the switch from latex to pdflatex took care of your issue.

The switch to pdflatex did enable table of contents, so if you pull from the git archive and do "make", you should see a PDF TOC.
Feb. 8th, 2011 02:21 pm (UTC)
API ease of use
Kudos for including a chapter on API ease of use in the book, but I find the content skeletal. What's the plan for that chapter?

Feb. 8th, 2011 08:42 pm (UTC)
Re: API ease of use
The plan for that chapter, as with the other chapters, is to fill it out over time. ;-)
Sep. 14th, 2011 12:14 am (UTC)
reader to RSS my feed
Yes there should realize the reader to RSS my feed to RSS commentary, quite simply
Sep. 19th, 2011 06:16 pm (UTC)
Re: reader to RSS my feed
You should be able to get RSS feeds from livejournal, if that is what you are asking for.
Oct. 3rd, 2011 03:19 am (UTC)
Agence de traduction
I just added this web site to my feed reader, great stuff. Can not get enough!

Latest Month

August 2017
Powered by LiveJournal.com
Designed by Tiffany Chow