10
$\begingroup$

Given the current trends with Moore's law and computer systems design, where even the cheapest cell phones and Raspberry Pi's, etc., are multi-threaded multi-processors, and any gains in performance (per Watt, per dollar, etc.) seem to be heading towards even more concurrent hardware:

How early should the concepts of parallel computation be introduced in computer science education (as the almost required default form of actual programming practice)?

What are the minimum prerequisite concepts before the requirement of concurrent thinking be introduced?

$\endgroup$
  • 1
    $\begingroup$ Basic knowledge of data structures is necessary, as a few synchronization mechanisms use queues. You could potentially include it in a data structures course IMO. pthreads could be confusing at this level, though. C++11 threads would be a better choice. $\endgroup$ – xuq01 May 24 '17 at 17:29
  • 1
    $\begingroup$ I didn't do a CS degree, but I did learn mutli threading at my first year of studying after high school, however it was because I had finished the past exercices already (i was quite above the level of our classe because I already practiced programmation before with PHP/web). I learned fork() and process intercommunication (pipe, socket, semaphore,file, ...) right before. $\endgroup$ – Walfrat Jul 31 '17 at 11:00
  • $\begingroup$ Maybe my memory is poor, but what I recall of my college degree program 30 yeas ago seems very limited and simplistic compared to what people seem to be learning in high school these days. Is it really that much better now? Why? $\endgroup$ – user737 Aug 8 '17 at 1:59
  • $\begingroup$ 30 years ago, the typical student PC did not have an OS that supported multi-threading or multiple processors. Whereas today, a typical student's mobile phone might expose quad or octo CPUs running 100's of processes. $\endgroup$ – hotpaw2 Aug 8 '17 at 2:37
10
$\begingroup$

If we don't introduce parallel/concurrent thinking early, our students can develop a sequential mindset that makes it hard for them to make the shift later. The rest of this is in the context of a college/university CS curriculum...

Multithreading can be discussed in CS1 if the students build GUIs, since the GUI needs its own thread to maintain responsiveness while the main thread is handling time-consuming GUI events. But most GUI libraries do this multithreading for you, so the students don't have to do it themselves -- you can talk about what's going on under the surface, but the students don't gain any hands-on experience and it's unclear to me how much they take away if they don't have to do it themselves. But there are schools that take this approach.

We introduce students to multithreading in CS2 (Data Structures), using Just-In-Time pedagogy. The basic idea is to give the students a problem that requires them to store a lot of data in a data structure (e.g., an organism's genome in a C++ vector or a Java ArrayList, or a really big image to be processed) -- enough data that processing the data sequentially takes 5-15 seconds. This is an eternity for todays students and they get impatient waiting so long for their program to solve the problem. We leverage that impatience and use it as motivation for introducing multithreading and parallel execution as a means of speeding up the program. We think the CS2 (Data Structures) course is the first time there is a natural motivation for introducing multithreading, since that's the first time you can store enough data to really motivate it.

Our CS3 course is an Algorithms course, so we continue the exposure there by introducing parallel versions of searching and sorting algorithms, graph algorithms, etc.

Our fourth course is Programming Languages, where we spend 1-2 weeks on languages that provide features for parallel / concurrent execution. For example, we contrast languages that expect threads to communicate via shared memory (and the different mechanisms to synchronize those accesses: semaphores, locks, condition variables, monitors) with languages that have threads communicate via message passing (e.g., Erlang, Scala).

Our sixth course is OS & Networking, where spend several weeks exploring the implementation of the features needed to do all of this: threads, processes, semaphores, locks, condition variables, message-passing systems, etc.

The upshot is that parallel and concurrency topics are "sprinkled" throughout our curriculum, rather than being confined to a single course. (We also offer a junior-senior elective course that focuses solely on parallel computing, so that students who want more can dig deeper into the subject.) That's one way to do it.

$\endgroup$
  • 3
    $\begingroup$ This is an excellent answer. Thorough, and we'll thought-out. Welcome to Computer Science Educators. I hope we get to hear more from you! $\endgroup$ – Ben I. Jun 24 '17 at 21:52
  • 2
    $\begingroup$ I like having concurrency spread over the whole curriculum as a concept, I think that makes a lot of sense and that's how we do it in high school level CS, too. I love the "leverage impatience" approach, too. But I'm not so sure about the first paragraph as a general statement ("introduce concurrency early to not lock students into a sequential mindset"), because getting concurrency right is hard - much harder than sequential thinking - and I don't think getting used to sequential solutions first actually makes later introduction of concurrency more difficult. $\endgroup$ – Pascal Jun 25 '17 at 12:34
5
$\begingroup$

We're introducing some aspects of parallel processing quite early on in Scratch. Each sprite has its own script which appears to execute in parallel with those of the others. Scratch has a broadcast and receive message protocol, and support for shared as well as private variables and lists.

Children might encounter this in a maze game, perhaps programming a number of similar ghosts to chase the player's avatar. It's also useful for agent-based modelling, e.g. the spread of an epidemic through a population.

Of course, it's not true multi-threading, as all of Scratch runs inside Flash, inside the browser, on just the one core, but I doubt those using Scratch will be aware of, or care about, the distinction.

This does, though, lead to potential difficulties in 'graduating' from Scratch to a text-based language such as Python - young Scratchers who've been used to programming in parallel in Scratch can find it hard to adjust to doing just one thing at a time in introductory Python programming.

$\endgroup$
  • $\begingroup$ Switching from Scratch to Python will probably feel like switching from space travel to inventing the wheel. $\endgroup$ – Gypsy Spellweaver Jun 13 '17 at 5:12
2
$\begingroup$

Given the type of software development that occurs these days, such as on mobile phones and with "big data" technologies, I think concurrency, threading, etc. should be introduced very early. Basically as soon as you start talking about what a program is, how it's invoked or executed, and what happens when it completes, I would discuss all that in the context of a concurrent environment. You don't necessarily need to get into all of the details initially but I would try to avoid teaching new students that all programs are sequential and uninterruptible.

$\endgroup$
2
$\begingroup$

In UK at A-level

We cover the following.

Multi-core, semaphores, queues, process pipeline, SISD, MISD, SIMD, MIMD.

We don't specifically cover how to write programs using these. A student could also get a good grade and know little about there.

$\endgroup$
2
$\begingroup$

I do not see much value in teaching more than an appreciation of threads and locking, until you have covered less primitive techniques for parallelism.

These techniques allow parallelism that scales beyond what threads and lock does, is easier to learn, and less prone to bugs.

  • Functional programming: Pure functional programmes do not have the concept of time, so can be re-arranged, and split across processors.
  • Pipeline programming: Writing programs to use a pipeline, to do some work and pass it to another process (sometimes used with process farms).
  • Transactional programming: Instead of asking a node for its state, then changing it, and passing back a new state (with lock). Pass a transaction (a bit of code) to the node, the node can then execute the transaction for you with out locks.
  • Immutable state: (see also functional programming.) If you don't change data then you don't have to lock it. Like a bank statement: it has a list of transactions, you can calculate the balance from these. Updating the balance requires a lock. Therefore don't update the balance. You may say the balance at the end of July is £5.43, but this is not the balance, it is the balance at a time.
  • SCOOP: Uses contracts to create thread safe code.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.