Cilk Programming Directory, Links. Development, Programmers, Programmer Reference, Resources @ eIT.in

Add Links: If you have a web site that you wish to include in this database, do let us know the details by sending a note about your URL to narsi@esource.in. We’ll quickly review the web site, and if found relevant, add it to the database. We look forward to web site owners and link exchange partners to submit URL. Thanks!

Looking for an outsourcing partner for software programming & development? Have you talked to us?

Other IT Web Sites from eIT.in

Content derived from Wikipedia article on Cilk

Cilk

From Wikipedia, the free encyclopedia

Cilk is a general-purpose programming language designed for multithreaded parallel programming.

Contents

1 Design

2 Basic parallelism with Cilk

2.1 Sample code

3 Advanced parallelism with Cilk: Inlets

4 Work-stealing

5 External links

Design

The major principle behind the design of the Cilk language is that the programmer should be responsible for exposing the parallelism, identifying elements that can safely be executed in parallel; it should then be left to the run-time environment, particularly the scheduler, to decide during execution how to actually divide the work between processors. It is because these responsibilities are separated that a Cilk program can run without rewriting on any number of processors, including one.

The Cilk language is based on GNU C, with the addition of just a handful of Cilk-specific keywords. When the Cilk keywords are removed from Cilk source code, the result is a valid C program, called the serial elision (or C elision) of the full Cilk program. Cilk is a clean extension of C and the serial elision of any Cilk program is always a valid serial implementation in C of the semantics of the parallel Cilk program.

The first Cilk keyword is in fact cilk, which identifies a function which is written in Cilk. Since Cilk procedures can call C procedures directly, but C procedures cannot directly call or spawn Cilk procedures, this keyword is needed to distinguish Cilk code from C code.

The remaining keywords are:

spawn

sync

inlet

abort

They are described in further detail below.

Basic parallelism with Cilk

Two keywords are all that are needed to start using the parallel features of Cilk:

spawn -- this keyword indicates that the procedure call it modifies can safely operate in parallel with other executing code. Note that the scheduler is not obligated to run this procedure in parallel; the keyword merely alerts the scheduler that it can do so.

sync -- this keyword indicates that execution of the current procedure cannot proceed until all previously spawned procedures have completed and returned their results to the parent frame.

Sample code

Below is a recursive implementation of the Fibonacci function in Cilk, with parallel recursive calls, which demonstrates the cilk, spawn, and sync keywords. (Cilk program code is not numbered; the numbers have been added only to make the discussion easier to follow.)

01 cilk int fib (int n)

02 {

03 if (n < 2) return n;

04 else

05 {

06 int x, y;

08 x = spawn fib (n-1);

09 y = spawn fib (n-2);

11 sync;

13 return (x+y);

14 }

15 }

If this code was executed by a single processor to determine the value of fib(2), that processor would create a frame for fib(2), and execute lines 01 through 05. On line 06, it would create spaces in the frame to hold the values of x and y. On line 08, the processor would have to suspend the current frame, create a new frame to execute the procedure fib(1), execute the code of that frame until reaching a return statement, and then resume the fib(2) frame with the value of fib(1) placed into fib(2)'s x variable. On the next line, it would need to suspend again to execute fib(0) and place the result in fib(2)'s y variable.

When the code is executed on a multiprocessor machine, however, execution proceeds differently. One processor starts the execution of fib(2); when it reaches line 08, however, the spawn keyword modifying the call to fib(n-1) tells the processor that it can safely give the job to a second processor: this second processor can create a frame for fib(1), execute its code, and store its result in fib(2)'s frame when it finishes; the first processor continues executing the code of fib(2) at the same time. A processor is not obligated to assign a spawned procedure elsewhere; if the machine only has two processors and the second is still busy on fib(1) when the processor executing fib(2) gets to the procedure call, the first processor will suspend fib(2) and execute fib(0) itself, as it would if it were the only processor. Of course, if another processor is available, then it will be called into service, and all three processors would be executing separate frames simultaneously.

(The preceding description is not entirely accurate. Even though the common terminology for discussing Cilk refers to processors making the decision to spawn off work to other processors, it is actually the scheduler which assigns procedures to processors for execution, using a policy called work-stealing, described later.)

If the processor executing fib(2) were to execute line 13 before both of the other processors had completed their frames, it would generate an incorrect result or an error; fib(2) would be trying to add the values stored in x and y, but one or both of those values would be missing. This is the purpose of the sync keyword, which we see in line 09: it tells the processor executing a frame that it must suspend its own execution, until all the procedure calls it has spawned off have returned. When fib(2) is allowed to proceed past the sync statement in line 11, it can only be because fib(1) and fib(0) have completed and placed their results in x and y, making it safe to perform calculations on those results.

Advanced parallelism with Cilk: Inlets

The two remaining Cilk keywords are slightly more advanced, and concern the use of inlets. Ordinarily, when a Cilk procedure is spawned, it can only return its results to the parent procedure by putting those results in a variable in the parent's frame, as we assigned the results of our spawned procedure calls in the example to x and y.

The alternative is to use an inlet. An inlet is a function internal to a Cilk procedure which handles the results of a spawned procedure call as they return. One major reason to use inlets is that all the inlets of a procedure are guaranteed to operate atomically with regards to each other and to the parent procedure, thus avoiding the bugs that could occur if the multiple returning procedures tried to update the same variables in the parent frame at the same time.

inlet -- This keyword identifies a function defined within the procedure as an inlet.

abort -- This keyword can only be used inside an inlet; it tells the scheduler that any other procedures that have been spawned off by the parent procedure can safely be aborted.

Work-stealing

The Cilk scheduler uses a policy called "work-stealing" to divide procedure execution efficiently among multiple processors. Again, it is easiest to understand if we look first at how Cilk code is executed on a single-processor machine.

The processor maintains a stack on which it places each frame that it has to suspend in order to handle a procedure call. If it is executing fib(2), and encounters a recursive call to fib(1), it will save fib(2)'s state, including its variables and where the code suspended execution, and put that state on the stack. It will not take a suspended state off the stack and resume execution until the procedure call that caused the suspension, and any procedures called in turn by that procedure, have all been fully executed.

With multiple processors, things of course change. Each processor still has a stack for storing frames whose execution has been suspended; however, these stacks are more like deques, in that suspended states can be removed from either end. A processor can still only remove states from its own stack from the same end that it puts them on; however, any processor which is not currently working (having finished its own work, or not yet having been assigned any) will pick another processor at random, through the scheduler, and try to "steal" work from the opposite end of their stack -- suspended states, which the stealing processor can then begin to execute. The states which get stolen are the states that the processor stolen from would get around to executing last.

External links

Cilk Project website at MIT

Retrieved from http://en.wikipedia.org/wiki/Cilk

End of Wikipedia content, http://en.wikipedia.org/wiki/Cilk

Web Resources for Cilk

More eIT.in References

o Programming Languages

§ The A-Z of Programming Languages

§ A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z

§ C

· C

· C++

· C#, CSharp Programming Language

· Caml

· CLU

· Cecil

· Centum

· Cilk

· Charity

· CHILL

· CLAIRE

· Clean

· COMAL

· CORAL

· Corn

· COBOL Programming

· CPL

· Ct

· Curl

Main Sections @ eIT.in

Software

· Free & Open Source Software

· Operating Systems

o Mainframe & Legacy Operating Systems

· Midrange

· Mainframe Operating Systems

· Databases

· Programming & Development Directory

o Programming Languages

§ The A-Z of Programming Languages

§ A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z

· Internet & Web

§ Web Servers

§ Application Servers

§ Server Side Scripting

§ Web Services

Computer Hardware
Networking & Communications Technologies
IT Strategy & Design
IT in Industries & Businesses
IT in Functions & Business Processes

IT Infrastructure
Tech Support
IT, Software Industry, Trade & Business Network
IT, Software Industry News & Updates

About eIT.in

eIT.in is a comprehensive directory for everything IT & Software. It contains over 500 categories, and well over 10,000 web resources

eIT.in provides directory and web links resources for the IT, software, programming & software development domains. It is intended to be useful for application, applications programmers & developers, software technology programmer & developer, databases software development, administrators & DBAs, application developers, strategy architect, design specialists and architects, migration, integration, customization consultants and customisation analysts, administration, maintenance & support professionals, outsourcing consultant, bespoke solutions programming developers & coders, project management & functional analyst, and for system administrators, testing & quality control engineers. It will make an effort to provide resources on tutorial/tutorials, guide, guides, tips, faq, faqs on these topics.

eIT.in content is available under GPL: All directory content at mainframe.in is under the General Public License (GPL). Under this license, anyone is free to copy & use any amount of directory content @ eIT.in, make changes to it and use it in any way they wish, as long as they also allow the same rights to anyone else for this content. The concept of GPL has been adapted from the GNU GPL of the Free Software Movement. To those who wish to use content from eIT.in, our only request is that they acknowledge the source and provide a link back to eIT.in. This is only a request!

Countries & Cities Where eIT.in Provides Assistance

eIT Cities: Bangalore, Chennai, Mumbai, Bhubaneswar, Mysore, Kolkaka, Delhi, Pune, Trivandrum, Hyderabad

United States of America - Alabama (AL) - Birmingham, Huntsville, Mobile, Montgomery, Arkansas (AR) - Little Rock, Arizona (AZ) - Phoenix, Tucson, California (CA) - Bakersfield, Fresno, Los Angeles, Modesto, Oakland, Orange Country, Riverside, Sacramento, Salinas, San Diego, San Francisco, San Jose, Santa Barbara, Santa Rosa, Stockton, Vallejo, Ventura, Visalia, Colorado (CO) - Colorado Springs, Denver, Connecticut (CT) - Hartford, Southern Connecticut (Southern Conn), Delaware (DE) – Wilmington, Florida (FL) - Daytona Beach, Fort Lauderdale, Fort Myers, Fort Pierce, Jacksonville, Lakeland, Melbourne, Miami, Orlando, Pensacola, Sarasota, Tampa, West Palm Beach, Georgia (GA) - Atlanta, Augusta, Hawaii (HI) – Honolulu, Iowa (IA) - Davenport, Des Moines, Idaho (ID) – Boise, Illinois (IL) - Chicago, Peoria, Rockford, Indiana (IN) - Fort Wayne, Gary, Indianapolis, Kansas (KS) – Wichita, Kentucky (KY) - Lexington, Louisville, Louisiana (LA) - Baton Rouge, Lafayette, New Orleans, Shreveport, Massachusetts (MA) - Boston, Springfield, Maryland (MD) – Baltimore, Michigan (MI) - Ann Arbor, Detroit, Flint, Grand Rapids, Kalamazoo, Lansing, Saginaw, Minnesota (MN) - Minneapolis – St. Paul, Missouri (MO) - Kansas City, St. Louis, Mississippi (MS) - Biloxi, Jackson, North Carolina (NC) - Charlotte, Greensboro, Hickory, Raleigh-Durham, Nebraska (NE) – Omaha, New Jersey (NJ) - Atlantic City, Bergen-Passaic, Jersey City, Mercer, Middlesex, Monmouth, Newark, New Mexico (NM) – Albuquerque, Nevada (NV) - Las Vegas, Reno, New York (NY) - Albany, Buffalo, Nassau-Suffolk, New York, Orange County, Rochester, Syracuse, Ohio (OH) - Akron, Canton, Cincinnati, Cleveland, Columbus, Dayton, Hamilton, Toledo, Youngstown, Oklahoma (OK) - Oklahoma City, Tulsa, Oregon (OR) - Portland, Salem, Pennsylvania (PA) - Allentown, Harrisburg, Lancaster, Philadelphia, Pittsburgh, Reading, Scranton, York, Rhode Island (RI) – Providence, South Carolina (SC) - Charleston, Columbia, Greenville, Tennessee (TN) - Chattanooga, Johnson City, Knoxville, Memphis, Nashville, Texas (TX) - Austin, Beaumont, Brownsville, Corpus Christi, Dallas, El Paso, Fort Worth, Houston, McAllen, San Antonio, Utah (UT) - Provo, Salt Lake City, Virginia (VA) - Norfolk, Richmond, Washington (WA) - Seattle, Spokane, Tacoma, Wisconsin (WI) - Appleton, Madison, Milwaukee, District of Columbia (DC) - Washington, DC

Canada

Provinces - Alberta > Cities: Calgary, Edmonton; British Columbia > Cities: Victoria, Vancouver; Prince Edward Island; Manitoba > Cities: Winnipeg; New Brunswick; Nova Scotia > Cities: Halifax; Nunavut > Cities: Iqaluit; Ontario > Cities: Toronto, Ottawa, Hamilton, London, Kitchener, St. Catharines-Niagara, Windsor; Quebec > Cities: Quebec City, Montreal; Saskatchewan > Cities: Saskatoon, Regina

Territories - Newfoundland and Labrador; Northwest Territories; Yukon Territory

Australia – Sydney, Melbourne, Brisbane, Perth, Adelaide, Newcastle, Gold Coast, Canberra, Wollongong, Sunshine Coast, Hobart, Geelong, Townsville, Cairns, Launceston

Europe - Luxembourg - Luxembourg City, Belgium – Brussels (Brussel), Antwerp (Antwerpen), Ghent (Gent, Gand), Charleroi, Liège (Liege), Austria - Vienna (Wien), Graz, Linz, Salzburg, Innsbruck, Netherlands - Amsterdam, Rotterdam, Utrecht, Eindhoven, Tilburg, ‘s-Gravenhage (sGravenhage), Groningen, France - Paris, Marseille, Lyon, Toulouse, Nice, Nantes, Strasbourg, Montpellier, Bordeaux, Germany - Berlin, Hamburg, Munich (München), Cologne (Köln), Frankfurt (Frankfurt am Main), Essen, Dortmund, Stuttgart, Düsseldorf, Bremen, Duisburg, Hannover, Nürnberg (Nuremberg), Dresden, Leipzig, Norway - Oslo, Bergen, Stavanger, Trondheim, Denmark – Copenhagen (Københavns), Aarhus (Århus), Odense, Aalborg (Ålborg), Sweden - Stockholm, Goteborg (Göteborg), Malmo (Malmö), Uppsala, Vasteras (Västerås), Finland – Helsinki (Helsingin), Espoo, Tampere (Tampereen), Vantaa, Turku, Oulu, Spain - Madrid, Barcelona, Valencia, Sevilla, Zaragoza, Malaga, Murcia, Las Palmas, Bilbao, Switzerland – Zürich (Zurich), Geneva (Geneve, Genève), Basel, Bern (Berne), Lausanne, UK - London, Birmingham, Glasgow, Liverpool, Sheffield, Leeds, Bristol, Manchester, Edinburgh, Leicester, Italy - Rome (Roma), Milan (Milano), Napoli (Naples), Torino (Turin), Palermo, Bologna, Firenze (Florence), Genova (Genoa)

eIT.in is a product of eSource India & Sourcing India

Other eSource & Sourcing sites: IT & Software (Dir, SAP), BPO, Chemicals, Textiles, Plant Oils, dotMobi, Billion Dollar Questions,

Biodiesel Encyclopedia, Linens, ideOS, Follars – Free, Open-source Dollars, Quali5.com – Own A Keyword Forever, AntiSE, Serkai, Leather & Hide, GeoDig