FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 | 5 |

«Communicating Process Architectures 2007 183 Alistair A. McEwan, Steve Schneider, Wilson Ifill, and Peter Welch IOS Press, 2007 c 2007 The authors ...»

-- [ Page 1 ] --

Communicating Process Architectures 2007 183

Alistair A. McEwan, Steve Schneider, Wilson Ifill, and Peter Welch

IOS Press, 2007

c 2007 The authors and IOS Press. All rights reserved.

C++CSP2: A Many-to-Many Threading

Model for Multicore Architectures


Computing Laboratory, University of Kent, Canterbury, Kent, CT2 7NF, UK.


Abstract. The advent of mass-market multicore processors provides exciting new op- portunities for parallelism on the desktop. The original C++CSP – a library providing concurrency in C++ – used only user-threads, which would have prevented it taking advantage of this parallelism. This paper details the development of C++CSP2, which has been built around a many-to-many threading model that mixes user-threads and kernel-threads, providing maximum flexibility in taking advantage of multicore and multi-processor machines. New and existing algorithms are described for dealing with the run-queue and implementing channels, barriers and mutexes. The latter two are benchmarked to motivate the choice of algorithm. Most of these algorithms are based on the use of atomic instructions, to gain maximal speed and efficiency. Other issues related to the new design and related to implementing concurrency in a language like C++ that has no direct support for it, are also described. The C++CSP2 library will be publicly released under the LGPL before CPA 2007.

Keywords. C++CSP, C++, Threading, Atomic Instructions, Multicore Introduction The most significant recent trend in mass-market processor sales has been the growth of multicore processors. Intel expected that the majority of processors they sell this year will be multicore [1]. Concurrent programming solutions are required to take advantage of this parallel processing capability. There exist various languages that can easily express con- currency (such as occam-π [2]), but the programming mainstream is slow to change lan- guages; even more so to change between programming ‘paradigms’. Sequential, imperative, procedural/object-oriented languages remain dominant. It is for this reason that libraries such as JCSP [3], C++CSP [4,5], CTC++ [6] and CSP for the.NET languages [7,8] have been developed; to offer the ideas of occam-π and its ilk to programmers who choose (or are constrained) to use C++, Java and the various.NET languages.

C++CSP has previously been primarily based on user-threads, which simplify the algo- rithms for the primitives (such as channels and barriers) as well as being faster than kernel- threads, but cannot take advantage of multicore processors. A review of the latter problem has given rise to the development of C++CSP2.

This report details the design decisions and implementation of C++CSP2 [9]. Section 1 explains the new threading model that has been chosen. Section 2 briefly clarifies the terminology used in the remainder of the paper. Section 3 provides more details on the implementation of the run-queue and timeout-queue. Section 4 describes how to run processes in a variety of configurations in C++CSP2’s threading model. Section 5 details a new barrier algorithm specifically tailored for the chosen threading model. Section 6 then presents benchmarks and discussion on various mutexes that could be used as the underpinning for many of C++CSP2’s algorithms. Section 7 contains details on the modified channel-ends and section 184 N. C. C. Brown / C++CSP2 8 discusses the channel algorithms. Section 9 highlights some issues concerning the addition of concurrency to C++. Finally, section 10 provides a brief discussion of networking support in C++CSP2, and section 11 concludes the paper.

Notes All the benchmarks in this report are run on the same machine; an Intel Core 2 Duo 6300 (1.9 Ghz) processor with 2GB DDR2 RAM. The ‘Windows’ benchmark was run under Windows XP 64-bit edition, the ‘Linux’ benchmark was run under Ubuntu GNU/Linux 64-bit edition.

C++CSP2 is currently targeted at x86 and (x86-64) compatible processors on Windows (2000 SP4 and newer) and Linux (referring to the Linux kernel with GNU’s glibc).

Windows is a registered trademark of Microsoft Corporation. Java is a trademark of Sun Microsystems. Linux is a registered trademark of Linus Torvalds. Intel Core 2 Duo is a trademark of Intel Corporation. Ubuntu is a registered trademark of Canonical Ltd. occam is a trademark of STMicroelectronics.

1. Threading

1.1. Background Process-oriented programming, based on CSP (Communicating Sequential Processes) [10] principles, aims to make concurrency easy for developers. In order to provide this concurrency, developers of CSP implementations (such as JCSP [11], CTJ [12], KRoC [13]) must use (or implement) a threading mechanism. When running on top of an Operating System (OS), such threading mechanisms fall into three main categories: user-threads, kernel-threads and hybrid threading models.

User-threads (also known as user-space or user-level threads, or M:1 threading) are implemented in user-space and are invisible to the OS kernel. They are co-operatively scheduled and provide fast context switches. Intelligent scheduling can allow them to be more efcient than kernel-threads by reducing unnecessary context switches and unnecessary spinning. However, they do not usually support preemption, and one blocking call blocks all the user-threads contained in a kernel-thread. Therefore blocking calls have to be avoided, or run in a separate kernel-thread. Only one user-thread in a kernel-thread can be running at any time, even on multi-processor/multicore systems. C++CSP v1.3 and KRoC use user-threads.

Kernel-threads (also known as kernel-space or kernel-level threads, or 1:1 threading) are implemented in the OS kernel. They usually rely on preemption to perform scheduling. Due to the crossing of the user-space/kernel-space divide and other overheads, a kernel-thread context switch is slower than a user-space context switch. However, blocking calls do not cause any problems like they do with user-threads, and different kernel-threads can run on different processors simultaneously. JCSP (on Sun’s Java Virtual Machine on most Operating Systems) uses kernel-threads.

Hybrid models (also known as many-to-many threading or M:N threading) mix kernelthreads and user-threads. For example, SunOS contained (adapting their terminology to that used here) multiple kernel-threads, each possibly containing multiple user-threads, which would dynamically choose a process to run from a pool, and run that process until it could no longer be run. Much research on hybrid models has involved the user-thread and kernelthread schedulers sharing information [14,15].

In recent years hybrid models have faded from use and research. The predominant approach became to increase the speed of kernel-threading (thereby removing its primary drawback) rather than introduce complexity with hybrid models and/or ways to circumvent userthreading’s limitations. This was most obvious in the development of the NGPT (Next GenN. C. C. Brown / C++CSP2 185 eration POSIX Threads) library for Linux alongside the NPTL (Native POSIX Thread Library). NGPT was a complex hybrid threading library, whereas NPTL was primarily centred on a speed-up of kernel-threading. NPTL is now the default threading library for Linux, while development of NGPT has been quietly abandoned.

1.2. C++CSP2 Threading Options This section explores the three different threading models that could be used for C++CSP2.

1.2.1. User Threads The previous version of C++CSP used only user-threads. With the mass-market arrival of multicore processors, the ability to only run on one processor simultaneously became an obvious limitation that needed to be removed. Therefore, continuing to use only user-threads is not an option.

1.2.2. Kernel Threads The most obvious move would have been to change to using only kernel-threads. In future, it is likely that the prevalence of multicore processors will continue to motivate OS developers to improve the speed of kernel-threads, so C++CSP would get faster without the need for any further development.

Channels and barriers between kernel-threads could be implemented based on native OS facilities, such as OS mutexes. The alternative would be to use atomic instructions – but when a process needed to wait, it would either have to spin (repeatedly poll – which is usually very wasteful in a multi-threaded system) or block, which would involve using an OS facility anyway.

1.2.3. Hybrid Model The other option would be to combine kernel-threads and user-threads. The proposed model would be to have a C++CSP-kernel in each kernel-thread. This C++CSP-kernel would maintain the run queue and timeout queue (just as the C++CSP kernel always has). Each process would use exactly one user-thread, and each user-thread would always live in the same kernel-thread.

It is possible on Windows (and should be on Linux, with some assembly register hacking) to allow user-threads to move between kernel-threads. However, in C++ this could cause

confusion. Consider a process as follows:

void run() { //section A out data;

//section B } With moving user-threads, the code could be in a different thread in section A to section B, without the change being obvious. If this was a language like occam-π, where the code in these sections would also be occam-π code, this may not matter. But C++CSP applications will almost certainly be interacting with other C++ libraries and functions that may not handle concurrency as well as occam-π. These libraries may use thread-local storage or otherwise depend on which thread they are used from. In these cases it becomes important to the programmer to always use the library from the same thread. So allowing user-threads to move would cause confusion, while not solving any particular problem.

186 N. C. C. Brown / C++CSP2 Moving user-threads would allow fewer kernel-threads to be created (by having a small pool of kernel-threads to run many user-threads) but the overheads of threading are primarily based on the memory for stacks, so there would not be any saving in terms of memory.

Another reason that hybrid models are considered inferior is that using priority can be difficult. A high priority kernel-thread running a low-priority user-thread would run in preference to a low-priority kernel-thread running a high-priority user-thread. However, C++CSP has never had priority so this is not yet a concern. I believe that the benefits of a hybrid threading model outweigh the drawback of making it difficult to add priority to the library in the future.

1.2.4. Benchmarks Benchmarking threading models directly is difficult. While context-switches between userthreads can be measured explicitly, this is not so with kernel-threads; we cannot assume that our two switching threads are the only threads running in the system, so there may be any number of other threads scheduled in and out between the two threads we are testing. Therefore the best test is to test a simple producer-consumer program (one writer communicating to one reader), which involves context-switching, rather than trying to test the context switches explicitly.

Four benchmark tests were performed. One test used user-threads on their own (without any kernel-threads or mutexes) and another test tested kernel-threads on their own (without any user-threads or C++CSP2 kernel-interactions). These ‘plain’ benchmarks reflect a choice of a pure user-threads or pure kernel-threads model. The two hybrid benchmarks show the result of using user-threads or kernel-threads in a hybrid framework (that would allow the use of either or both). See Table 1.

Table 1. Single communication times (including associated context-switches) in microseconds.

–  –  –

1.2.5. Analysis It is apparent that kernel-threads are at least ten times slower than user-threads. The nature of the benchmark means that most of the time, only one kernel-thread will really be able to run at once. However, these times are taken on a dual-core processor which means that there may be times when less context-switching is needed because the threads can stay on different processors. For comparison, the ratio between user-threads and kernel-threads on single core Linux and Windows machines were both also almost exactly a factor of ten.

For simulation tasks and other high-performance uses of C++CSP2, the speed-up (of using user-threads rather than kernel-threads) would be a worthwhile gain. However, running all processes solely as user-threads on a multi-processor/core system would waste all but one of the available CPUs.

A hybrid approach would allow fast user-threads to be used for tightly-coupled processes, with looser couplings across thread boundaries. Using a hybrid model with kernelthreads would seem to be around 15% slower than ‘plain’ kernel-threads. If only kernelthreads were used by a user of the C++CSP2 library, the hybrid model would be this much slower than if C++CSP2 had been implemented using only kernel-threads. In fact, this deficit is because no additional user-threads are used; much of the time in the hybrid model benchN. C. C. Brown / C++CSP2 187 mark is spent blocking on an OS primitive, because the user-thread run-queue is empty (as explained in section 3.1). This cost would be reduced (or potentially eliminated) if the kernelthread contained multiple user-threads, because the run-queue would be empty less often or perhaps never.

A hybrid approach flexibly offers the benefits of user-threads and of kernel-threads. It can be used (albeit with slightly reduced speed) as a pure user-thread system (only using one kernel-thread), or a pure kernel-thread system (where each kernel-thread contains a single user-thread, again with slightly reduced speed), as well as a combination of the two. Therefore I believe that the hybrid-threading model is the best choice for C++CSP2. The remainder of this paper details the design and implementation of algorithms for the hybrid-threading model of C++CSP2.

2. Terminology

Pages:   || 2 | 3 | 4 | 5 |

Similar works:

«A NEEDS ANALYSIS OF PAKISTANI STATE BOARDING SCHOOLS SECONDARY LEVEL STUDENTS FOR ADOPTION OF COMMUNICATIVE LANGUAGE TEACHING By HAMID ALI KHAN A dissertation submitted to the School of Arts & Education of Middlesex University, London in part fulfilment of the requirements for the degree of MA TESOL (2006-7) SUPERVISORS: CLARE O’DONOGHUE/ JULES WINCHESTER August, 2007 ABSTRACT English language teaching has become very important because of the global status of English and people all over the...»

«19 Sodom, Gomorrah and The Days of Noah! A queer nation and a queer world are bringing about the destruction of America and the world. God’s judgments will soon be poured out on this generation, as it was on the generation of Noah, and the cities of Sodom and Gomorrah. God will not be mocked, or ignored, much longer Here are the facts – and the consequences of a world gone wild. William F. Dankenbring In the great Mount Olivet prophecy, detailing the signs of the times which would point...»

«SLUMMING AND THE 19th CENTURY GEOGRAPHICAL IMAGINATION by JAMES MATTHEW TOWEILL A THESIS Submitted in partial fulfillment of the requirements for the degree of Master of Arts in the Department of English in the Graduate School of The University of Alabama TUSCALOOSA, ALABAMA 2010 Copyright James Matthew Toweill 2010 ALL RIGHTS RESERVED ABSTRACT The act of slumming helped define and partition the 19th century US city. Intimately connected with slumming was its representation in prose works. By...»

«Andrews Uniuersity Seminuy Studies, Summer 1981, Vol. 19, No. 2, 99-114 Copyright O 1981 by Andrews University Press.THE EXEGETICAL METHODS OF SOME SIXTEENTH-CENTURY PURITAN PREACHERS: HOOPER, CARTWRIGHT, AND PERKINS PART 11* ERWIN R. GANE Pacific Union College Angwin, California In Part I of this series, I provided a brief overview of the preaching careers of the three Puritan preachers here under consideration-John Hooper, Thomas Cartwright, and William Perkins. I also analyzed their concept...»

«Library Article   Getting acquainted with. Bowzer’s Digestive System Written by: Linda Aronson, DVM This is the first in an occasional series on the different systems making up the Beardie’s body and some of the things that can go wrong with them. The past three months we have looked at the various components of our beardies’ diets. Now, we’d like to take you on a trip with that food as it passes through your beardie. At the beginning: We have already talked about teeth (Beardie...»

«VOLUME 1. ISSUE 1 ISSN: 000 000 000 FINANCIAL PLANNING RESEARCH JOURNAL Challenges facing financial planners Journal of the advising ageing clients with diminished Financial Planning financial capacity John Teale Association Just how safe are ‘safe withdrawal rates’ of Australia in retirement? Michael E. Drew & Adam N. Walk The conflict between financial decision making and indigenous Australian culture Suzanne Wagland & Sharon Taylor A (W)hole in financial budget: Budgeting’s influence...»

«PRESBYTERY OF WESTERN NORTH CAROLINA ADDENDUM July 26, 2016 Children’s Hope Alliance Grandfather Home Campus Banner Elk, North Carolina ADDENDUM D-7 THE PRESBYTERY OF WESTERN NORTH CAROLINA COMMITTEE ON MINISTRY REV. WHIT MALONE, CHAIR JULY 26, 2016 SECOND SECTION The Book of Order provides that the Committee on Ministry may be given authority by the Presbytery to find in order calls issued by churches, to approve and present calls for service of ministers, to approve the examination of...»

«Vendor Kit 2014 Exhibitor & “Pulling For Patients Challenge” Saturday June 21, 2014 Peterborough Airport (CYPQ) Global Angel Charitable Organization 925 Airport Rd., Peterborough ON K9J 6X7 Telephone: 705 740 2645 Fax: 705 741 5147 www.globalangelcharity.com info@globalangelcharity.com Our 2014 Theme is to Honour our Everyday Heroes who Protect our Borders and Serve our Communities Now is your chance to be a part of an exciting event being held for the first time at the newly expanded...»

«Hard Words from the Prophets Jeremiah 16:1-4, 9-13, Revelation 3:14-22, Matthew 23:29-39 Rev. Peter Sawtell, Eco-Justice Ministries ministry@eco-justice.org This morning, we heard three texts that are rarely used in sermons. None of these passages ever appear in the Revised Common Lectionary, so many pastors never have the opportunity to wrestle with them. You may be glad that they don't show up in the 3-year cycle of lectionary readings, because they are texts of despair and judgment. They...»

«Community Engagement Toolkit: Creating a Campaign Plan Groundswell | 1850 M Street NW, Suite 1150 | Washington, D.C. 20036 202.505.3051 | www.groundswell.org | @grndswell Building Demand through Community Engagement This toolkit is designed for individuals and organizations implementing local community engagement campaigns. These resources provide a framework for organizing community demand for energy services. These successful tactics emerged from our experience implementing a local community...»

«Am J Hum Genet 35:645-651, 1983 Congenital Glaucoma Due to Dominant Goniodysgenesis. A New Concept of the Heredity of Glaucoma TORD JERNDAL1 SUMMARY Three typical pedigrees with hereditary glaucoma are presented, in which dominant goniodysgenesis is shown to be the actual genetic trait. Because of a marked variation in the expressivity of dysgenesis, the symptoms of the genetic malformation (elevated intraocular pressure and subsequent glaucoma) may appear early or late in life. Therefore,...»

«Death of Liku Onesi following collision with a Police vehicle INTRODUCTION 1. At about 8.39am on Wednesday 22 August 2012, a Police patrol responding to a report of a burglary in progress collided with a vehicle being driven by Ikenasio Onesi on Ormiston Road, Flat Bush.2. Liku Onesi, Mr Onesi’s wife and passenger in the vehicle, died as a result of injuries sustained in the collision.3. The Police notified the Independent Police Conduct Authority of the incident, and the Authority conducted...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.