Talk:Parallel computing

From Wikipedia, the free encyclopedia

Featured article star Parallel computing is a featured article; it (or a previous version of it) has been identified as one of the best articles produced by the Wikipedia community. Even so, if you can update or improve it, please do.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Featured article FA rated as FA-Class on the assessment scale
Top rated as Top-importance on the assessment scale
Archive
Archives

Archive 1


Contents

[edit] Questions?

Is this statement in the article referring to interlocks?

Only one instruction may execute at a time—after that instruction is finished, the next is  executed

--Ramu50 (talk) 03:13, 15 June 2008 (UTC)

What is an interlock? I've never heard this term used in any parallel computing sense. Raul654 (talk) 03:19, 15 June 2008 (UTC)

[edit] Rewrite

This article is really bad - even the first sentence has a non-trivial error ("Parallel computing is the simultaneous execution of some combination of multiple instances of programmed instructions and data on multiple processors in order to obtain results faster" -- this totally ignores ILP). I'm going to rewrite it. I don't have my copies of Patterson and Hennessey handy - they're in my office. I'll pick them up from the office tomorrow. In the meantime, I've started the rewrite at User:Raul654/PC Raul654 04:11, 28 October 2007 (UTC)

Note - I'm about halfway finished. Raul654 04:31, 6 November 2007 (UTC)

Raul - this is a nice, well illustrated article. While I can understand your redirecting Concurrent computing to here, I think you are being a tad overzealous in redirecting Distributed computing to this page. You've consigned the entire subject under the rather obscure-sounding subheading of "Distributed memory multiprocessing". Suddenly, Wikipedia seems to have lost the rather important subject of Distributed computing! Please reconsider your action and undo the redirect on Distributed computing. That page may still need more work, but it's way too big a sub-topic of parallel computing to cram into this page. - JCLately 06:18, 7 November 2007 (UTC)

Actually, I was very careful to define "distributed computing" in the very first paragraph of the article as computing across computers connected by a network (and cite a reference for that definition) Under the classes I have laid out here, that would be distributed memory multiprocessing (which includes clusters and MPPs) and grid computing - which is a *very* accurate definition. At the same time, I think you are exaggerating (greatly) the distinction between parallel computing and distributed computing. Raul654 06:23, 7 November 2007 (UTC)
I'm too tired to do this justice right now, but I'll at least make one brief reply before I hit the sack. I won't argue with your formal classification of the subject area, but the term "parallel computing" generally connotes broader and more fundamental aspects of parallelism that come up in the design of processors and supercomputers. Distributed computing may be conceptually equivalent, but practically speaking, the introduction of significant distances and greater autonomy in distributed systems is a big deal. It brings in issues of networking, databases, and the wonderful world of middleware. This is too much to cover in under "Parallel computing", and I'd venture to guess that most people who are interested in distributed computing - a very hot topic - would not be so interested to read about the generalities and fundamental issues covered nicely on this page. I'm guessing that you have a somewhat academic perspective on this subject, which is not universally shared - that may be an understatement. - JCLately 06:49, 7 November 2007 (UTC)
After some thinking, I've reworked that section: I've renamed distributed memory multiprocessing to distributed computing (the two are exactly synonomous) and put grid computing under that heading. I don't consider database/network/middleware discussion to warrant a separate distributed computing article (those topics should more properly be discussed in the specific articles like cluster and grid computing). But if you want distributed-computing specific discusion, there is space under that heading now. Raul654 16:59, 7 November 2007 (UTC)
I agree that renaming the section from "distributed memory multiprocessing" to "distributed computing" is an improvement, but I do not share your view that the general topic of distributed computing is unworthy of its own page. Consider the fact that a Google search on the phrase "distributed computing" yields 1.7 million hits, which happens to be somewhat more that the number of hits for the phrase "parallel computing". Also note that Wikipedia's "What links here" lists over 500 other WP pages that link to Distributed computing, and the number of WP links to Parallel computing is somewhat less. Even if we set aside the rather substantial editing implications of the redirect you proposed, is there a good reason to presume that all of those links to Distributed computing really should have pointed to the broader topic of Parallel computing? Certainly, these terms are not synonymous.
The analogy that comes to mind is the relationship between physics and chemistry. From the physicist's point of view, chemistry is just the physics of tightly bound configurations of fermions. And your acknowledgment of grid and cluster computing as legitimate topics is akin to recognizing the subfields of organic and inorganic chemistry, but being for some reason unwilling to acknowledge the broader field of chemistry. That's about as far as I can go with that analogy, because distributed computing doesn't break down quite so neatly: the concept of grid computing is rather fuzzy, and might be regarded by some as a buzzword. Cluster computing isn't quite so fuzzy, but there is a great deal to be said about distributed computing that doesn't specifically belong under either cluster or grid computing. At least the topic of distributed computing has the virtue of being widely recognized as meaningful. (Incidentally, I don't think "Massive parallel processing" in the sense of MPP supercomputer architectures really belongs under Distributed computing, but that's a different issue.)
From your perspective, the database/network/middleware aspects may be of only passing interest, but to many people interested in distributed computing those considerations - and let me add security to the list - these are issues of paramount interest. Returning to my analogy, someone interested in chemistry is not looking for a page that discusses quarks and gluons. Given that there are a number of subtopics of distributed computing that are worthy of their own separate pages, and there also exists an extensive category tree for Category:Distributed computing, can there be any reasonable doubt that Distributed computing is a topic worthy of its own page? - JCLately 04:31, 8 November 2007 (UTC)

[edit] Suggested new first paragraph

Hi, below is a suggestion for a new introductory paragraph. Comments? henrik•talk 06:51, 9 November 2007 (UTC)

Parallel computing is a form of computing in which many operations are carried out simultaneously. Parallel computing operates on the principle that large problems can almost always be divided into smaller ones, which may be carried out concurrently ("in parallel"). Parallel computing has been used for many years, mainly in high performance computing, but interest has been renewed in later years due to physical constraints preventing frequency scaling. Parallel computing has recently become the dominant paradigm in computer architecture, mainly in the form of multicore processors.

I like it. Raul654 12:20, 9 November 2007 (UTC)
Me too. Arthur 18:03, 9 November 2007 (UTC)
Thanks! henrik•talk 19:40, 9 November 2007 (UTC)

I would like the article to talk about dependencies, pipelining and vectorization in a slightly more general way (i.e. not tied to parallelism as in thread parallelism or a specific implementation in a processor), as well as using slightly different terminology. I've started to type up some notes at User:Henrik/sandbox/Parallel computing notes. But I'm a little bit hesitant to make so major modifications to a current WP:FAC article, so I thought I'd bring it here for discussion first. Your thoughts would be appreciated. henrik•talk 19:40, 9 November 2007 (UTC)

What do you think of this first line
Parallel computing is a form of computing in which multiple processors are used to allow many instructions to be carried out simultaneously.
I think it needs to be clear that multiple processors are required.
Also, is "compute resource" the correct term? I thought it was a typo but it is used repeatedly Mad031683 21:44, 14 November 2007 (UTC)
"processor" is (pretty much) synonymous with a von Neumann machine, but there are other methods of doing parallel computing, such as dataflow machines, ASIC or FPGA algorithm implementations, superscalar and vector processors (where there is parallelism within a single von Neumann control logic), et cetera. Granted, single von Neumanns are the vastly most prolific form of "compute resource", so if the consensus is that it is too pedantic to avoid the word "processor", I won't be the one starting an edit war :-) henrik•talk 21:54, 14 November 2007 (UTC)
The definition as quoted in the cited source says "processing elements" which is more accurate terminology, IMO. Raul654 23:18, 14 November 2007 (UTC)

[edit] Things to do

Things left from the old FAC nom that need to be addressed before renominating:

  1. Expand the history section. Links: http://ei.cs.vt.edu/~history/Parallel.html, http://ctbp.ucsd.edu/pc/html/intro4.html, http://www.gridbus.org/~raj/microkernel/chap1.pdf
  2. Discuss more about the software side (languages)
  3. Make references consistent

After those are done, renominate on FAC. Raul654 (talk) 20:36, 10 December 2007 (UTC)

[edit] Section 1.4

This section is very odd. How is fine-grained and coarse-grained parallelism related to communication between subtasks at all? The granularity is strictly related to computation length, not communication frequency. —Preceding unsigned comment added by Joshphillips (talk • contribs) 22:38, 19 December 2007 (UTC)

False. Granularity is the amount of time/computation between communication events (or, more strictly speaking, the ratio of time between computation and communication) Raul654 (talk) 22:45, 19 December 2007 (UTC)

[edit] Good article nomination

I have just finished reviewing this article for good article (GA) status. As it stands, I cannot pass it as a GA due to some issues outlined below. As such, I have put the nomination on hold, which allows up to seven days in which editors can address these problems before the nomination is failed without further notice. If and when the necessary changes are made, I will come back to re-review it.

GA review (see here for criteria)
  1. It is reasonably well written.
    a (prose): b (MoS):
    The section on data parallelism needs some tidying. The main article on it explains it quite well, but the section in this article should summarise the main article. Additionally, the paragraph about loop carried dependencies needs further explanation and/or an example, as the text is currently unclear and the linked article is non-existent.

    The history section needs a bit of work also; I feel that it needs to be a bit more in-depth about the progression of parallel computing rather than just picking a couple of milestones to highlight.
  2. It is factually accurate and verifiable.
    a (references): b (citations to reliable sources): c (OR):
    Seems fairly well-referenced to me. The only issue I have (which would not preclude me from passing it as a GA) is with the labelling of the various references to the two Hennessy/Patterson books: after the first full references (i.e. title, publisher etc), one is referred to as Hennessy and Patterson and the other as Patterson and Hennessy. Personally I find this a touch confusing but am unsure exactly how to solve it short of using full references in all of the citations (which is not ideal either).
  3. It is broad in its coverage.
    a (major aspects): b (focused):
    Nicely covers the background and then focuses on the various topics well.
  4. It follows the neutral point of view policy.
    Fair representation without bias:
    Article appears to be NPOV.
  5. It is stable.
    No edit wars etc.:
    Recent history indicates the article to be stable.
  6. It is illustrated by images, where possible and appropriate.
    a (images are tagged and non-free images have fair use rationales): b (appropriate use with suitable captions):
    There is no fair use rationale for Image:Cell Broadband Engine Processor.jpg (used in the section 'Multicore computing'). Additionally, I don't feel that the use of the image passes the fair use policy, most specifically section 8 (Non-free content is used only if its presence would significantly increase readers' understanding of the topic, and its omission would be detrimental to that understanding).
  7. Overall:
    Pass/Fail:
    The article is certainly within reach of achieving GA status once the issues outlined above are addressed. My reasoning for putting it on hold, as opposed to failing it outright, is that I feel the sections I outlined above just need some expanding and tidying, which I feel could be achieved in the seven day hold period. I would welcome any comments or queries about the points I have raised, but would prefer them to be made here on the talk page (as opposed to my user talk) so that all editors involved with the article are aware of them. Blair - Speak to me 01:43, 6 January 2008 (UTC)

I have expanded the discussion of loop carried dependencies. Raul654 (talk) 19:00, 6 January 2008 (UTC)

One thing: the example for loop-carried dependencies seems wrong to me - it illustrates the point, but it doesn't seem to be calculating the Fibonacci numbers as stated. If I'm reading it correctly, PREV and CUR are initialised to 0 and 1 respectively. Inside the loop, PREV is then set to CUR i.e. PREV = 1. CUR is then calculated as PREV + CUR = 2. This then repeats to give PREV = 2, CUR = 4 and then PREV = 4, CUR = 8 and finally PREV = 8, CUR = 16 before the loop exits. In other words, the output (counting the initialisations) is 0, 1, 2, 4, 8, 16 as opposed to the expected Fibonacci series 0, 1, 1, 2, 3, 5, 8, 13.
The problem seems to be a read-after-write hazard. I would personally write the pseudocode for a Fibonacci series as
1: prev1 := 0
2: prev2 := 0
3: cur := 1
4: do:
5:    prev1 := prev2
6:    prev2 := cur
7:    cur := prev1 + prev2
8: while (cur < 10)
If my calculations are correct, this would then output the Fibonacci terms as expected. I would be bold and change this myself, but I would like to double-check that I am not misreading the current example. Additionally, I am not sure which is the better example - the existing one (if the text is corrected to match) is simpler to understand, however a good compiler would optimise it away. As an aside, it would probably end up as a left-shift as this corresponds to multiplying a binary-represented number by two, which is what the contents of the loop are doing.
Also, apologies for being a couple of days late with coming back and reviewing your changes - works been busy and I am currently hunting for a new flat to live in this year. It looks good to me; I am about to pass this as a good article. The example issue is relatively minor (I don't think many people will be investigating it in such detail as myself) and will be fixed shortly in whatever way is decided here (including the possible decision that I am blind and misreading it!). For my two cents, I would stick with the Fibonacci series idea.
Congratulations and thank you for your efforts on this article. Feel free to use one of the templates in Category:Wikipedia Good Article contributors on your userpage.
Blair - Speak to me 09:36, 16 January 2008 (UTC)

[edit] Distributed systems redirect

I don't think this redirect necessarily is appropriate: a distributed system is not just a computer concept (an organisation of employees is a distributed system). I think there should be a separate article, hyperlinking to this one, on the wider concept. Any thoughts? ElectricRay (talk) 10:51, 21 January 2008 (UTC)

Thank you for pointing this out. In fact, I would (and did) argue that a similar redirect is uncalled-for, even within the context of programming and computer science. See the Talk section above, under "Rewrite". I just checked what redirects to this article, and was surprised to discover that many other inappropriate redirects had previously escaped my notice. I believe these should also be removed, or moved to the appriate article(s). - JCLately (talk) 15:21, 21 January 2008 (UTC)
agree with the thrust of your posts above. I don't have the information to write a separate article (except by way of original research) but in terms of non-computing components the sort of thing I had in mind is this (and this is definitely WP:OR, so not suitable for the enyclopaedia itself):
in a non-digital context, a "network" might be used generically to denote any means by which any spatially dispersed members of single system or community interacts. No need for common purpose or intentionality (eg a city: it has no common purpose). The End-to-end principle is substrate-neutral and applies equally to any such system: An effective bottom layer of such a network needs (a) to preserve sufficient integrity and structure of movement/interpretation/communication so that there is as much flexibility to impose complexity on the edge of the network as possible and (b) the network is otherwise as agnostic as possible about those complexities.
Clearly one needs to define a minimum structure so that the system will work and thereafter (to optimise the ability to impose complexity), the highest common factor of all user needs of *all* feasible system users. (If you define your users and their needs in terms of, for example, negotiating derivatives transactions, you will come up with a bottom layer which looks like an ISDA Master Agreement, which gives huge flexibility within the context of a derivatives trading relationship but a fair bit of inbuilt (& functional) complexity too, which saves time at the periphery, as long as all you are doing is trading derivatives. If you tried to use ISDA as a system for broadcasting news, it would be far less functional.
Other examples of the "simple system; complex overlay":
  • "Natural" languages (like English) and the speciality language that develops atop it (Legalese, computer jargon, local idioms and dialects)
  • rail network against a road network - for users, the trains, carriages and time of delivery and destinations are fixed by the network, and individual users don't have much choice/flexibility about how they are used. This works well where there are large number of users all of whom need to move between a limited number of discrete points in predictable numbers at predictable times. But a train service wouldn't work so well in a relatively low density population with no central hub point (or an insufficently limited number of points of usual travel) (perhaps one reason why there's no metropolitan rail service in Los Angeles).
  • By contrast a road network is cheaper to maintain and run (less complexity in base network: no prescribed means of conveyance on the network and relatively little constraint on usage (traffic lights etc); scope for greater flexibility/complexity on the part of the user), but is in a way more prescriptive on the user in terms of rules of the road (these are mostly transparent to. Note a user can create a greater level of system complexity (akin to a rail service) on top of the road network - by running a bus service - which might not be quite as efficient as a rail service (in the right population environment) but is cheaper and doesn't (much) interfere with the residual flexibility of users to design other means of using the nework (in that they are also free to walk, run, ride, cycle, or drive a hovercraft as long as they comply with minimum rules of the road).
  • Challenge is to craft suitable rules of the road that prevent cars and buses colliding but otherwise enable free and fast movement of traffic.
  • Owners of various parts of the network can overlay their own rules if they wish as long as a user who doesn't need them has another way of getting to her destination (the beauty of a nodal network)
I'd be astounded if I were the first person to ever make that connection (Lawrence Lessig has done something similar in Code Version 2.0), but I don't have the background to know who it was. I sure would like to, though. ElectricRay (talk) 09:57, 22 January 2008 (UTC)

[edit] architectures

I'm tempted to delete a few occurrances of this word and just write "computers" as in:

  • Some parallel computers architectures use smaller.....
  • While computers architectures to deal with this were devised... GrahamColmTalk 13:20, 4 May 2008 (UTC)

[edit] Ideal program runtime and others

  1. Program runtime can not decrease in linear with increasing the number of processors even in ideal case (as it is shown in "Parallelization diagram").
  2. Does the article make any distinction between words "serial" and "sequential" in the context of computing paradigm?
  3. Do you consider important to mention any theoretical model for parallel computing (PRAM for example)?
  4. Article lacks at least to mention some impossibility results in the context of P-Completness theory and the notion of inherently sequential problems, do you agree?, kuszi (talk) 07:42, 17 May 2008 (UTC).
To answer your questions: (1) You're wrong. In the ideal case, a program has no sequential bottleneck and parallelizes with 100% efficiency. (2) There is no difference between "sequential" and "serial" processing. The article uses both terms interchangeably. (3) No, mathematical models of parallel computing are a dime a dozen. (4) I don't understand this question. Raul654 (talk) 17:56, 17 May 2008 (UTC)
(1) Are you sure? Even when efficiency is 100% it is difficult to have runtime below 0. (2)Thank you. (3,4) Possibly the mathematical models for parallel computing are easy to find, however it would be nice to at least mention to the reader that such models exists and that we can, for example, distinguish between NC and P-complete problems. 85.128.91.247 (talk) 05:15, 19 May 2008 (UTC). I was logged out, sorry, kuszi (talk) 10:21, 19 May 2008 (UTC).

One more thing:

  1. Last sentence in the introduction: The speedup of a program as a result of parallelization is given by Amdahl's law. - objection here, possibly the potential speedup or something alike? kuszi (talk) 10:21, 19 May 2008 (UTC).

[edit] Consistent terminology

This article uses the terms speed-up and speedup. I think they're both ugly, but whichever is to be preferred, then the article ought to be consistent. --Malleus Fatuorum (talk) 03:36, 15 June 2008 (UTC)