Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Teaching Concurrency (2009) [pdf]

research.microsoft.com

Post reply on HN
Print view View original

11–20 of 47 posts

Re: Teaching Concurrency (2009) [pdf]

#11

Post by Const-me »

TickleSteve wrote: post #4

I think the first thing people should be taught about concurrency... is when not to use it. Concurrency can result in increased maintenance costs and complexity. Concurrency is also not more efficient on a single core. Concurrency can help with latency and response time. In embedded systems in particular, there is an over-use of concurrency which often results in bloated, complex code.

> Concurrency is also not more efficient on a single core.

Concurrency can be more efficient even on a single core. When blocking synchronous I/O is involved, concurrency may help saturate the bandwidth with multiple in-flight requests.

Re: Teaching Concurrency (2009) [pdf]

#12

Post by InclinedPlane »

Const-me wrote: post #9

When I was a kid, I loved playing transport tycoon deluxe videogame. When I grew up to be a programmer, never had much problems with concurrent stuff. IMO designing concurrent programs is conceptually similar to building complex high-throughput low latency railway networks in the game.

Related: https://deadlockempire.github.io/

Re: Teaching Concurrency (2009) [pdf]

#13

Post by argv_empty »

Const-me wrote: post #10
argv_empty wrote: post #2

The only actionable advice in here for someone tasked with developing a curriculum for teaching concurrency is to make sure the prerequisite courses instill the idea of computation as a sequence of state transitions.

“Sequence of state transitions” implies you can order them by time. Generally, various state transitions happen in parallel, their relative order is undefined even on an SMP system. You can serialize the transitions if you want, but that usually costs performance. This is especially true for distributed parallel computing, where the state is also distributed.

It sounds like you're modeling the state space wrong. In a concurrent system, the state is not just one thread's (or one processor's, or one machine's) internal data (including program counter). That would be like saying a (single-threaded) program's state is the contents of the registers and topmost stack frame. The state in a concurrent system is the combination of every thread's internal state. And what actually happens is a sequence of such arrangements. One arrangement is not realized without replacing the previous one.

Re: Teaching Concurrency (2009) [pdf]

#14

Post by rdmsr »

Const-me wrote: post #9

When I was a kid, I loved playing transport tycoon deluxe videogame. When I grew up to be a programmer, never had much problems with concurrent stuff. IMO designing concurrent programs is conceptually similar to building complex high-throughput low latency railway networks in the game.

An open source version (remake?) of the game exists[1].

[1] https://www.openttd.org/en/

Re: Teaching Concurrency (2009) [pdf]

#16

Post by Const-me »

argv_empty wrote: post #13
Const-me wrote: post #10

Earlier quoted context omitted.

“Sequence of state transitions” implies you can order them by time. Generally, various state transitions happen in parallel, their relative order is undefined even on an SMP system. You can serialize the transitions if you want, but that usually costs performance. This is especially true for distributed parallel computing, where the state is also distributed.

It sounds like you're modeling the state space wrong. In a concurrent system, the state is not just one thread's (or one processor's, or one machine's) internal data (including program counter). That would be like saying a (single-threaded) program's state is the contents of the registers and topmost stack frame. The state in a concurrent system is the combination of every thread's internal state. And what actually h…

I’m aware the state you were talking includes state of all threads.

When you combine several sequences of state transitions (one sequence per thread), you don’t get another sequence of state transitions. When two CPU cores perform two state transitions at the same time, you typically cannot determine whichever of those transitions happened first.

We might have different definitions what’s sequence. I mean this: https://en.wikipedia.org/wiki/Sequence As you see, global order is required for bunch of elements (in this case, state transitions) to form a sequence. And in concurrent and especially parallel programming, there’s no global order for those transitions. Hence, those transitions don’t form a sequence.

Re: Teaching Concurrency (2009) [pdf]

#17

Post by argv_empty »

Const-me wrote: post #16
argv_empty wrote: post #13

Earlier quoted context omitted.

It sounds like you're modeling the state space wrong. In a concurrent system, the state is not just one thread's (or one processor's, or one machine's) internal data (including program counter). That would be like saying a (single-threaded) program's state is the contents of the registers and topmost stack frame. The state in a concurrent system is the combination of every thread's internal state. And what actually h…

I’m aware the state you were talking includes state of all threads. When you combine several sequences of state transitions (one sequence per thread), you don’t get another sequence of state transitions. When two CPU cores perform two state transitions at the same time, you typically cannot determine whichever of those transitions happened first. We might have different definitions what’s sequence. I mean this: https…

No, we just have different notions of system state. If we have a pair of, say, Turing machine heads on one tape that aren't necessarily moving in lockstep, I say that the system state is the tape contents, the two heads' locations, and the two heads' states. A transition for this system can be either or both heads moving either direction, overwriting the symbol they're pointing at, and changing its own internal state. The state {tape="000111000", head0loc=0, head0state=2, head1loc=4, head1state=6} might transition to {tape="000101000", head0loc=0, head0state=2, head1loc=5, head1state=2}, or it might transition to {tape="100111000", head0loc=1, head0state=2, head1loc=4, head1state=6}, or to {tape="100101000", head0loc=1, head0state=2, head1loc=5, head1state=2}. In a given run of the system, one of those is what actually happens. Then another happens after that, and so on. So we get a sequence of them.

A transition is not one machine head changing its position and state. {head0loc=0, head0state=2}->{head0loc=1, head0state=2} is not a transition because that does not identify a pair of whole-system states.

Re: Teaching Concurrency (2009) [pdf]

#18

Post by Const-me »

argv_empty wrote: post #17
Const-me wrote: post #16

Earlier quoted context omitted.

I’m aware the state you were talking includes state of all threads. When you combine several sequences of state transitions (one sequence per thread), you don’t get another sequence of state transitions. When two CPU cores perform two state transitions at the same time, you typically cannot determine whichever of those transitions happened first. We might have different definitions what’s sequence. I mean this: https…

No, we just have different notions of system state. If we have a pair of, say, Turing machine heads on one tape that aren't necessarily moving in lockstep, I say that the system state is the tape contents, the two heads' locations, and the two heads' states. A transition for this system can be either or both heads moving either direction, overwriting the symbol they're pointing at, and changing its own internal state…

> one of those is what actually happens

No it’s not. If the heads aren’t moving in lockstep, what actually happens is you’ll extremely rarely have a moment of time when both locations are whole numbers.

At one moment you have { head1loc=0, head2loc=4.17 }, head #1 reached the cell position on the tape, head #2 is still moving. After a while, you’ll have { head1loc=0.872, head2loc=5}, head #1 is on its way, head #2 reached the cell position.

Looks like for a Turing machine with two asynchronously moving heads, there’s no usable concept of “state” at all. That’s very close to what happens when doing actual parallel programming on real hardware.

Good luck applying your idea of computation as a sequence of state transitions to that.

Re: Teaching Concurrency (2009) [pdf]

#19

Post by argv_empty »

Const-me wrote: post #18
argv_empty wrote: post #17

Earlier quoted context omitted.

No, we just have different notions of system state. If we have a pair of, say, Turing machine heads on one tape that aren't necessarily moving in lockstep, I say that the system state is the tape contents, the two heads' locations, and the two heads' states. A transition for this system can be either or both heads moving either direction, overwriting the symbol they're pointing at, and changing its own internal state…

> one of those is what actually happens No it’s not. If the heads aren’t moving in lockstep, what actually happens is you’ll extremely rarely have a moment of time when both locations are whole numbers. At one moment you have { head1loc=0, head2loc=4.17 }, head #1 reached the cell position on the tape, head #2 is still moving. After a while, you’ll have { head1loc=0.872, head2loc=5}, head #1 is on its way, head #2 re…

Even if a Turing machine were a physical object (I had thought you would be aware that it's not), either one of those moves completes before the other, or both complete simultaneously.
Post reply on HN