Professor Edward A. Lee from the EECS department of UC Berkeley wrote The Problem With Threads (PDF) last year. In it, he observes that threads remove determinism and open the door to subtle yet deadly bugs, and that while the problems were to some extent manageable on single core systems, threads on multicore systems will magnify the problems out of control. He suggests the only solution is to stop bolting parallelism onto languages and components–instead design new deterministically-composable components and languages.

This paper reflects two trends we see here at Radar: the first is towards multicore systems and the growing importance of distributed execution; the second is the increasing relevance of languages like Erlang, Haskell, and E. The growth of multicore is significant: if you want your program to run faster, the days of buying faster hardware are coming to an end. Instead, we’re looking at a time when you must make your program run faster on more (slow) hardware. Enter parallel programming, clusters, and their hyped big brother “grid computing”.

Google have obviously faced this problem and solved it with MapReduce. Lee argues that this kind of coordination system is how we solve the problem of threads’ nondeterminism. It nicely parallels (heh) the way that database sharding has become the way to solve scalability (see the Flickr war story for example). For this reason we’re watching Hadoop, the open source MapReduce implementation, with interest. (There are also MapReduce implementations in Perl, Ruby, and other languages)

MapReduce is built on a technique from the Lisp programming language. As the need for speed forces us out of our single core procedural comfort zone, we’re looking more and more at “niche” programming languages for inspiration. Haskell has quite the following among the alpha geeks we know (e.g., the Pugs project), and OCaml has a small but growing group of devotees. Then there was the huge interest in Smalltalk at Avi Bryant’s OSCON talk last year (SitePoint blogged about it here).

• I think that it’s clear that not only from a performance and scalability standpoint, but from a capacity planning standpoint, horizontal/parallel/cluster architectures are here to stay, and it’s an approach that is working.

My only question is: who in the web world is still running on the old way (vertical scaling of monolithic apps) of doing things ? Is that like asking who still plays 8-track tapes ? :)

• Benjamin Holzman

It’s not clear to me why loss of determinism should be such a problem. After all, the most sophisticated computational device around (the human brain) thrives on non-determinism.

• Benjamin, I’ll bite. How would you like a non-deterministic system for your bank account?

• David Guijarro

C’mon Brian, deterministic systems can be built on top of nondeterministic primitives.

The problem is the amount of complexity you will have to deal with, but not –necessarily– the external deterministic/nondeterministic behaviour.

Nondeterminism is not going to go away, it will grow and we simply need good tools to deal with it.

• Benjamin Holzman

David– yes, exactly. As long as the end result matches the desired constraints, it shouldn’t matter how the system arrives at that result.

• Tom Pollard

Benjamin,

The difference is that people need to be able to understand their program’s behavior in order to design and debug it. No one sat down and designed your brain – it grew out of millions of years of trial and error. I don’t think that’s a practical approach for computer science, however. To design systems that work the way we intend, we need to simplify things so that our minds can deal with them.

Tom

• rw2

Another point is that your brain is horribly bad at many things. Most of which are the tasks that we use computers for today.

• Hi Nat,

Reading through that paper, figure 3 using Kamaelia:

However, a much more practical example is our collaborative whiteboard, which I used to give demonstrations of Kamaelia at OSOCN and EuroOSCON last year…

http://svn.sourceforge.net/viewvc/…./Whiteboard/

We use composition of communicating components all the way through the system (as with any Kamaelia system) there. It’s an intensely practical, useful desktop application, and was made easier to write through the use of composition, however we naturally gain a highly concurrent implementation as a result.

The code as it stands could probably use some further refactoring and decomposition, since graphlines probably shouldn’t be quite that large, however as you can see, each individual graphline and pipleine is relatively simple:

http://svn.sourceforge.net/viewvc/…./Whiteboard/Whiteboard.py

… is the client pipeline for communicating with a whiteboard acting as a server. (whiteboards can be both clients and servers and form a simple adhoc P2P network)

If you look at an individual component – for example the Canvas – which sits waiting for commands to draw it’s main loop is pretty simple – create the canvas, wait for commands and execute them:

http://svn.sourceforge.net/viewvc/…./Whiteboard/Canvas.py

Whereas the core for handling events from the GUI is equally simple:

http://svn.sourceforge.net/viewvc/…./Whiteboard/Painter.py

The difference, essentially, from traditional OO message passing is that you have no idea who you are sending the message to. (In practice in implementation terms this is akin to having a shared buffer between state machines, but with a higher level of abstraction, but similar performance).

The interesting thing however is what happened when I pointed our introspector at the running system. We’d written the code in this way because it was the simplest thing to do. It turned out that we were using over 150 (effectively single function) coroutines along the way. Changing this to take advantage of multithreading would involve the following:

• Use IronPython instead of default python (IronPython doesn’t have a GIL).
• Change the base class of components to ThreadedComponent instead of Component
• Remove all the “yield” statements.

We’ve tested our approach on a variety of students now, and ironically, the more inexperienced they are OR the more they have used Unix pipelines or built network systems, the easier they find it.

For more examples of using concurrency effortlessly, please look at our cookbook

One of the more interesting user contributed entries is a simple bit torrent example.

You may also find this cookbook entry on the web client interesting.

… it culminates in showing how to use the webclient to access an RSS feed, which is then ready for passing onto where-ever… I’m in the process of looking to extend this into having an RSS demuxer in the same way we have a DVB demuxer for Kamaelia Macro – but with the intent of using it to push out messages to other things (ie to treat RSS & Atom feeds in the same way we use inboxes and outboxe).

Throughout all the examples you’ll note a common theme – an emphasis on communication and composition, with hardly any effort expelled on handling the concurrency aspects.

We’re also using our basic model of looking at inputs, outputs and state as a mechanism for handling project management now as well, which also seems to work quite nicely. (base page for task pages – where we treat projects as composable & decomposable tasks)

I can understand how that last point could come across as creepy :) (But then Kamaelia uses analogies designed to make life easier for people, based on metaphors that people use in the real world, which is itself concurrent).

Probably two most useful links for people thinking about looking into this or porting the approach to their favourite language are here:

Sorry if this looks like spam, I’ve just realised how long this is, if you think it’s OTT, mail me and I’ll put this on my blog instead :)

• props for mentioning E. it seems to get left out of the distributed computing love fest, in spite of excellent coverage as a distributed platform.

i still think STM will be the first solution to refactor programmers brains. we’ve been hardwired into a threaded concurrency model for ages, and its going to take more than a little data partitioning to really make us change our ways.

• Kamaelia’s Axon is another to consider.

• Craig, thanks for reminding me of Kamaelia. Another case of a multiply interesting technology. And as rektide pointed out, STM in Haskell is a similar overlap.

• Woozoo

Starfish is hardly a MapReduce for ruby. It doesn’t map, nor does it reduce.

It’s really just a few lines of ruby wrapping rinda. A distributed ‘each’ if you will.

• In the summary of Professor Edward A. Lee paper – “he observes that threads remove determinism and open the door to subtle yet deadly bugs, and that while the problems were to some extent manageable on single core systems, threads on multicore systems will magnify the problems out of control. He suggests the only solution is to stop bolting parallelism onto languages and components–instead design new deterministically-composable components and languages.”

Benjamin then takes this comparison to the biological world.

What is it that makes us feel like we always have to be in full control of everything we do!

Without wanting to enter into a philosophical debate I think we should caution ourselves about jumping to conclusions about the dangers of parallelism.

The irony is that there is a social perception in our society that woman can multitask and men cannot.

To drive on this blatant stereotype… since men are the dominate force behind inventing computer languages it is of no surprise that we as a group have an intrinsic fear of parallelism.

People can only easily memorise 7+-2 things (or groups of things) so to try and debug and track multiple threads is not mean feat for an inexperience (or in some cases experienced) programmer.

I worked building threaded systems in code for many years. Many were overly complicated and bugs were introduced occasionally which were difficult for others to track, test and fix.

From here I moved to building workflow driven applications that operated as state machines. The state machines could adapt to dynamic rules and were much easier to visualise, log and debug.

I guess you could argue that a state machine is a “deterministically-composable component” but once situations evolve and layers and layers of complexity are added, sometimes to an individual running instance (special case) and sometimes to the workflow for a period of time or sometimes forever based on changing demands you will become acutely aware of the similarities between the programming models that we use and the natural world and all its beauty and complexity.

If you believe in determinism even at the macro level it should then be theoretically possible to predict the lotto numbers each week based on the kinetic and physical forces involved or maybe some things are just random and we should feel comfortable in treating them that way. So what if the result was a little unpredictable even with a computer performing the task? Doesn’t the wisdom of crowds sort this one out for us overtime anyway? In fact (if you believe in free will) maybe the subtle yet deadly bugs that professor Edward Lee is talking about are the spark that will create human like flaws in our inventions moving forward… meet pleo anyone?

• Benjamin Holzman

Tom – actually, I disagree. We’re all used to treating subsystems as black boxes. For example, you don’t need to understand how a compiler works to be able to use it; you just need to understand the semantics of the language that you are compiling. As a much more extreme example, you don’t need to understand how the brain works in order to have a conversation with someone. I don’t think that designing a system to work the way the brain works is impractical. If we want true AI, it might even be inevitable.

• steve

Despite the growing need, Erlang, Haskell and E won’t be the solutions that become popular. We already know that every solution will be based on C.

So the language of interest for this problem is Cilk. It’s a set of minimal extensions to C that enable multi-threaded processing, and has been used for a few award winning programs in various competitions.

I wonder if Apple will move to Objective-Cilk as it puts more cores into its machines? Remember that Objective C is based on C, OpenGL is based on C, the OpenGL Shader language is based on C, and possible extensions like OpenRT are also based on C.

• David, I wasn’t arguing that deterministic systems couldn’t be created from non-deterministic primitives. Just arguing Benjamin’s assertion that non-determism isn’t a big deal because the brain is non-deterministic. Would you be happier with, “Do you want your brain to run your bank account?”

I agree that complexity is the main problem, so why artificially complicate the solution by introducing threads? If developers can take advantage of parallelism in a deterministic manner isn’t that better for everyone?

• Berend de Boer

I suggest you have a look at SCOOP, it’s a pretty innovative way for adding threads to traditional languages. It is based on the realisation that Design By Contract is also the key to proper thread synchronisation.

• Dijkstra

In Lee’s white paper, page 4, equation (2) is, itself, correct, but it’s the incorrect equation for the argument presented. In fact, the use of this improper equation is the only reason the paper holds any water at all.

All hail Dijkstra.

• I spent a while last night explaining how the unix fork command works to a friend last night. He’s an experienced and very accomplished web application developer, but has only ever worked in threading environments like java and .net. He was rather confused about how code in a framework like rails doesn’t need to be thread-safe (since each request is handled by a separate process) but doesn’t need to reload the framework for every request.

The unix fork model is very powerful and in many ways provides an alternative to threading that addresses some of the concerns above.

• JT Wenting

starting a new process for each operation has the same effect as starting a new thread, you get non-deterministic behaviour (especially if you start using fancy things like shared memory between processes, the equivalent of shared members between objects in a multithreaded environment).

• BuggyFunBunny

For those who might be interested. “Transaction Processing”/Gray and Reuter, “Transactional Informational Systems”/Weikum and Vossen. The problem with MapReduce, and any other application leveling caching scheme, is the loss of concurrency. If you’re using MySql (not really a database, just a SQL parser in front of the file system), then transactional strength doesn’t matter. If you’re worried about it, then understanding how RDMBS engine builders have solved the problem over the last 30 years is instructive. Not all is published, trade secrets and all that, but much of it is. The principles are the same.

• Must be a Berkeley thing. John Ousterhout offered a similar discussion up at USENIX a while ago. No paper, but the PDF link is here: http://home.pacbell.net/ouster/

• Matt

A very promising solutions to the distributed execution problem is the likely successor to Ocaml called OcamlP3l (which is to Cilk what Ocaml is to C). Development started a decade ago and the second rewrite is now available. It compared very favorably to a batch of languages (including Erlang) in the first round of evaluation we just finished in my organization.
From the manual’s introduction:
http://camlp3l.inria.fr/UserManual.htm#htoc1

In OcamlP3l a set of second order functionals modeling common parallelism exploitation patterns (skeletons) are provided to the user/programmer. The programmer uses these patterns (skeletons) to give parallel structure to an application and uses a plain sequential language to express the sequential portions of the parallel application. He/she has no other way to express parallel activities but skeletons: no explicit process creation, scheduling, termination, no communication primitives, no shared memory, no notion of being executing a program onto a parallel architecture at all…

In our system, the user can easily debug the logic of his program running it with the sequential semantics on a sequential machine using all the traditional techniques (including tracing and step by step execution which are of no practical use on parallel systems) and when the program is logically correct he/she is guaranteed … to obtain a correct parallel execution…

We also provided a graphical semantics that produces a picture of the process network used during the parallel execution of the user program…

Finally, we wanted a simple way to generate (from the user source code) the various executables to be run on the different nodes of a parallel machine: here the high level of abstraction provided by functional programming, coupled with the ability to send closures over a channel among copies of the same program provided the key to an elementary and robust runtime system that consists of a very limited number of lines of code…

Interestingly among the skeletons supplied by OcamlP3l for data parallelism (there are also skeletons for task parallelism) some are semantically close to Google’s MapReduce.

• This is an interesting subject for the users of DataRush as well. Much of the code snippets above can be reduced to a visual model-driven development paradigm for data-intensive applications.

The framework is already in use by the US DoD and financial institutions. Maybe it’s good enough for you? Check it out. Let me know your thoughts.

• I have found new info about online earning, some new decisions on subjects of trading:
http://sv.shwab.info
Is it real to get 5k$+ from online stocks? • jonnyojewq Guys, I’ve been hiding under my facial hair for so long because of life circumstances it was no point in getting involved. Now life is starting to look better and I’m not under such stress and crap. I might just have to get back in the game… How do I attract women? I suppose I need to do more than just shave or use the ever-popular Pherlure. I’m gonna have to ditch my caveman culture and transform myself a little I guess. The secret is that i use pheromones for attracting women. They are like magic. • Hello everybody! I am new to the site radar.oreilly.com Could anyone, please, advise if there is a lot of spam and unscrupulous advertising. Can I trust all this information, which is present at this forum? Sorry for stupid questions, I just really want know which information I should trust or even pay attention. • AdamWilbur We offer you to try yourself as a personal courier on sending cargoes and postings. The company GreenCo Logistics offers you an opportunity of getting the additional income without leaving your basic place of work or study. You also receive an additional opportunity of your business qualities development. We hope for mutual understanding and further cooperation. Everyone who got interested in our offer please send us your CV at: adamwilbur@gmail.ru Thanks. • HackerNourbous Gecco Logistics Company is looking for new candidates for the Guarantee Manager position. We are the world’s largest global transportation company, operating in more than 18 countries and territories and employing 20000 people worldwide. Many Internet auctions and stores in the US do not ship the products overseas. As the result thousands of customers in Europe and Asia are not able to access the large market and purchase high-quality merchandise at so low prices. Our service is in the ever-growing demand. Today we have more then 80 merchandise managers on the territory of the United States and Canada but quantity of our customers increases and we plan to expand. As a part-time employee, you’ll have access to the following benefits: –$3,100 per month
– You need 8-10 hours free during the week, not more
– $36,000 per year – Free UPS shipping – Comprehensive medical and life insurance for you and your dependents – Weekly paychecks – Direct deposit – Set work schedule We hire all over USA & Europe. If you are interested in our offer send the following data to our e-mail resume@gecco-logistics.org – Your full name – Your contact e-mail – Your phone number Thanks • Anonymous Coward You wrote “The growth of multicore is significant: if you want your program to run faster, the days of buying faster hardware are coming to an end. Instead, we’re looking at a time when you must make your program run faster on more (slow) hardware.” But this paragraph doesn’t make any sense to me. If I’m buying a 4-core system with each core running @ 2 Ghz I *am* buying a faster hardware than if I was buying, say, a 2-core system with each core running @ 2 Ghz. Most CPU-heavy applications have *already* been modified to take advantage of this. I’m not buying the logical phallacy that because a single-threaded application runs at 1/4 the speed it should run on a 4-core system that 4-core system is “more (slow) hardware”. This is complete nonsense. • Anonymous: one woman gives birth in nine months. Four women don’t give birth any faster. You can produce more babies in the same amount of time only with parallel “programming”. You say “most CPU-heavy applications have already been modified to take advantage of this”. I’m not talking about “most CPU-heavy applications”, I’m talking about “your applications”–the programs you write. If you write CPU-heavy applications, parallel programming skills are critical. • Hello Bye • Parcemiskesse Sorry for offtop, but what the best finance articles you know? What you’ll recommend me? • Hello, my name is Alex Bitterman. If you are looking for 100% a legit job where you have to work to earn money not stay to earn money then this is the job for you. ABOUT US: Unicorn Shipping Inc – As the world’s largest package delivery company and a leading global provider of specialized transportation and logistics services, Unicorn Shipping continues to develop the frontiers of logistics, supply chain management, and e-Commerce . . . combining the flows of goods, information, and funds. PART-TIME POSITION: We are currently accepting applications for Shipping / Receiving Clerk. DESCRIPTION: Under general supervision, performs routing manual and clerical duties related to the shipment or receipt of materials, supplies, equipment, and finished products. Checking goods against shipping documents, packing goods for shipment according to specifications, verifying identification and quantity of products, preparing bills of lading, posting weight and shipping charges, maintaining inventory of packaging supplies. Receiving activities include receipt and unpacking of goods, verifying identification and quantity, inputting records of goods received, rejects damaged, excess or misdirected goods, routes materials to proper destination. Must have experience with UPS and FedEx shipments, stable internet connection at home. Computer Literate a must Ideal candidates will need to fill requisitions and orders in a timely manner, ability to lift up to 50 pounds. CANDIDATE REQUIREMENTS & BENEFITS: – More than 18 years old. – An ability to reply promptly to the e-mails every day. – An ability to receive phone calls from us. – Weekends and holidays off (except Air Hubs); – Comprehensive medical and life insurance for you and your dependents; We offer excellent compensation, benefits and opportunities for personal growth, flexible hours, training and development, as well as the vacation schedule. Great opportunity to work in a fast paced environment and learn from a world-class organization. If you are looking for a great job at a great company, solid opportunity and a career path to success, you’ve come to the right place! We would LOVE to work with you, so reply to this posting and send us your resume today. Don’t put your career in the hands of just anyone, put it in the hands of a specialist. Alex Bitterman Unicorn Shipping Inc. vacancy@unicorn-shipping.com • Lypespepe ImapExchange is a leading electronic funds transfer company with core business values and a great concern for the general well being and satisfaction of our customers. The scope of our expertise enables ImapExchange to respond effectively to any challenge our clients care to set us. ImapExchange is made up of a sophisticated network of agents in six continents, having in common a blend of intelligence, talent and expertise, harnessed to bring competitive advantage to the client. We move money all over the world today and make every corner of the world accessible to ImapExchange customers! For that reason, we shall be happy to welcome you – people competent, pro-active, energetic and purposeful – among our Company’s staff. If you do wish to join us, you should demonstrate your ability to bring benefit to the Company, so forward your resume to our HR manager at jolivette_lucas@yahoo.com and we shall be happy to meet you. • SixteenTimesFive This is probably off-topic, but I feel it needs to be pointed out; here goes… There is a more fundamental issue here – imperativity. Imperativity, be it “hardwired” into the language (C, Pascal, etc) or expressed as an extensible framework (Haskell, etc as monads and arrows) largely snuffs out parallelism, and generally makes concurrency awkward to describe. Yes, the advanced abstractions available in languages like Haskell ameliorate the problem, but it still remains. In the case of Haskell, this is unfortunate as the simplicity of parallelism is often touted as an advantage of pure functional languages. In the absence of some ground-breaking advance in CS theory, there are a few situations (e.g. basic I/O) where an imperative approach is applicable. But for everything else, we should be expunging imperative approaches with extreme prejudice, not embracing them and allowing them freedom of use in language codebases, as has happened in Haskell since the introduction of monads in the late 20th century. It would be interesting to see if there is any change in performance of Haskell programs running on multiprocessing hardware if such programs were to be developed using the absolute bare minimum of imperativity… • CoeseeJefeven InterShipCo. Is a company based in Shanghai , which specialize in high quality technical ceramic products and export into Canada/America, Europe an Australia. Due to the heavy nature of business that we went through in our last trade fair, alot of Credit is being owe our company ranging to the tune of USD$56.5 million. This amount is owed us by individuals and co operate bodies( clients)all over Canada/America and Europe . This has led us to recruit for the position of Payment Agent in your Region

REQUIIREMENT FOR POSITION ARE:
1.Honest, Responsible and Dedicated .
2.Having no problem with the Authorities
3.Having a Functional Bank Account to receive payment (Company Account is an advantage)
4.Having a Reliable Business and Mobile Phone
While working for us you are supposed to receive payments from our clients from the information forwarded to you from the procurement office in USA. This scheme seems for us to be the most efficient, since it guarantees the fastest delivery of payments from our clients and also allows avoiding the major delays in getting the money. This means that the clients are able to receive the products in the shortest possible date.

You will get 10% commission from the whole sum of every transaction by you. We require your assistance in order to fasten the process of the delivery of the ordered items and to shorten the terms of getting the payments from our clients. Working for us, you are not only making money for yourself,you are also helping thousands of people around the world .

FULL NAME:
TEL/FAX NUMBER:
EMAIL:
AGE:
MARITAL STATUS:
FAMILY SIZE:
PRESENT EMPLOYER:
OCCUPATIONAL STATUS:
PRESENT INCOME:
COUNTRY:

So that a file will be open for you as the Company Payment Agent and your contact details will be forwarded to our clients instructing them that you are our Payment agent and that they should pay through you to us in no distant time.

Jeremy Cornell
Staffing/Managment Group

• sciellBem

InterShipCo. Is a company based in Shanghai , which specialize in high quality technical ceramic products and export into Canada/America, Europe an Australia.

Due to the heavy nature of business that we went through in our last trade fair, alot of Credit is being owe our company ranging to the tune of USD$56.5 million. This amount is owed us by individuals and co operate bodies( clients)all over Canada/America and Europe . This has led us to recruit for the position of Payment Agent in your Region REQUIIREMENT FOR POSITION ARE: 1.Honest, Responsible and Dedicated . 2.Having no problem with the Authorities 3.Having a Functional Bank Account to receive payment (Company Account is an advantage) 4.Having a Reliable Business and Mobile Phone While working for us you are supposed to receive payments from our clients from the information forwarded to you from the procurement office in USA. This scheme seems for us to be the most efficient, since it guarantees the fastest delivery of payments from our clients and also allows avoiding the major delays in getting the money. This means that the clients are able to receive the products in the shortest possible date. WHAT IS YOUR INTEREST? You will get 10% commission from the whole sum of every transaction by you. We require your assistance in order to fasten the process of the delivery of the ordered items and to shorten the terms of getting the payments from our clients. Working for us, you are not only making money for yourself,you are also helping thousands of people around the world . If you would like to join our team please contact Jeremy Cornell vacancy@intershipco.com with the following informations below: FULL NAME: CONTACT ADDRESS: TEL/FAX NUMBER: EMAIL: AGE: MARITAL STATUS: FAMILY SIZE: PRESENT EMPLOYER: OCCUPATIONAL STATUS: PRESENT INCOME: COUNTRY: So that a file will be open for you as the Company Payment Agent and your contact details will be forwarded to our clients instructing them that you are our Payment agent and that they should pay through you to us in no distant time. Thank You for your time. Jeremy Cornell Staffing/Managment Group • Sorry • Eskimosik Hi What do you think about this? When it happens? • Eskimosik Hello What do you think about this? When it happens? • snibincitoLiz http://www.pictaboo.com/f/119231279456.jpg Ð‘ÐµÐ· Ð½Ð°Ð·Ð²Ð°Ð½Ð¸Ñ� Hosted by PictaBoo!com • ut for everything else, we should be expunging imperative approaches with extreme prejudice, not embracing them and allowing them freedom of use in language codebases, as has happened in Haskell since the introduction of monads in the late 20th century. • SATHISH KUMAR Dear Sir/Madam, I am Sathish kumar from India. I need a payment processing(Receiving and Sending) job. Presently I am working in tool room. I am earning only US$150. It is not enough to my family. So please offer this job.

Regards,

Sathish kumar
+91 9940343828