Converting flowchart to pseudocode

[sandy.bridge]

Interesting. So not only is there a race condition, both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct? From what I know, you start at "START", and end and "STOP", and therefore those conditions would not be able to be represented between START and STOP.

 

[gneill]

Interesting. So not only is there a race condition, both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct? From what I know, you start at "START", and end and "STOP", and therefore those conditions would not be able to be represented between START and STOP.

That's more or less it. While it's possible to write "dead code" in pseudo code (just put a branch around it), I don't think there's a way to exactly reproduce the structure of such a race condition.

 

[rcgldr]

both 1=1? conditions cannot really be converted to pseudo-code because there is no path from the start box to those conditions, correct?

One method for multi-threading psuedocode is to use sequences. All sequences in this example would start and run at the same time in parallel. To duplicate the race condition in your flowchart with pseudocode, but without the uneeded conditionals:

sequence
    x = 1
endsequence

sequence
    x = 0
endsequence

sequence
    if(x == 1)
        then docleverthing
endsequence

CH USB gaming controllers includes a scripting language that uses this same syntax (sequence , endsequence), for multi-threading, except it's sequences continously loop. Generally the sequences wait for controller button presses / releases, or continously convert physical controller inputs to virtual controller outputs (this is done at some fixed sampling rate that is adjustable).

The structure of the race condition flow chart is faulty. You can't have 3 parallel threads of code merge into a single thread. What the flowchart should look like is 3 flow charts with starts and stops, but sharing a common variable, x. Treat each thread as if it's running on it's own processor, and that only memory (in this case "x") is shared. There shouldn't be any arrows connecting the "x = 0" thread and the "x = 1" thread into the "x == 1?" thread, since these are independent threads. For example, you could consider the "x=0" and "x=1" threads as input devices with dma access to the variable x, and these input devices could not switch into the context of executing code from the "x == 1?" thread.

 

[sandy.bridge]

So are the threads going to come together at any joints at all? Or are we merely running the three threads at the same time?

 

[gneill]

The structure of the race condition flow chart is faulty. You can't have 3 parallel threads of code merge into a single thread.

Well, the point is that by the given rules the flowchart is valid. Whether or not it is meaningful or "correct" is another matter Not my fault if the rules are faulty or incomplete!

Cray had a form of parallelism called autotasking, implemented at the compiler/library level. With it logical threads could be spawned, merged, and dismissed automagically. For example, a DO LOOP might automatically be split into several portions to be worked on by separate tasks (threads), then the results merged upon completion. The language (a version of FORTRAN) didn't have to explicitly specify the action at each instance. Threads simply joined the fray, results merged, and then disappeared leaving a single serial thread to carry on. While all the logically correct details were managed below the surface, the code that the user wrote and saw simply looked like a typical single-thread serial code.

 

[rcgldr]

So are the threads going to come together at any joints at all? Or are we merely running the three threads at the same time?

You're running three threads at the same time, at least initially. The flow chart implies that the three threads become one thread where the arrows connect in at the middle.

The flowchart would be valid if those arrows from the outer threads connecting to the inner thread represented termination of those outer threads, and that the inner thread was pending on completion of both outer threads (order not important, so you still have the race condition) before continuing. This would be the windows equivalent of the inner thread doing a WaitForMultipleObjects() on an array of 2 thread handles for the outer threads (order of thread termination would not be important).

Cray had a form of parallelism called autotasking, implemented at the compiler/library level. With it logical threads could be spawned, merged, and dismissed automagically.

The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads. On the CDC and Cray machines (and I assume many current processors), some out of order and parallel operations on registers were handled via register "scoreboarding", a hardware scheme which was used to indicate that a register was "waiting" for the output from some operation, suspending any operations wanting to use that register as input. I don't think there was any form of hardware "scoreboarding" for memory, so that required a software handshake (mutex, semaphore, ...).

Scoreboarding dates back to the CDC 6600 (1964) (about a year before the first IBM 360 was delivered):

http://en.wikipedia.org/wiki/Scoreboarding

 

[sandy.bridge]

Why exactly can't it be converted into pseudo-code then? I'm seeing the race condition and how the program can fail but I am not seeing how it cannot be converted into pseudo-code.
For example:

Do A1=0

Do A1=1

If A1==1
{

somethingClever​

}

 

[rcgldr]

Why exactly can't it be converted into pseudo-code then?

It can be converted into psuedo code, but you need a convention on how to describe parallel threads with pseudo code, and operators that can pend on actions (including spawning and termination) between threads.

 

[gneill]

You're running three threads at the same time.

Depends on how "flowchart" was defined. Normally you can't have multiple states at the same instance in a flowchart, so the control flow can only be at one point in the flow chart at any time. In this case the flow chart starts with 3 control flows, then ends up with one.

The flowchart would be valid if those arrows from the outer threads connecting to the inner thread represented termination of those outer threads, and that the inner thread was pending on completion of both outer threads (order not important, so you still have the race condition) before continuing.

In this case we can only assume the rules are as given, no more, no less. Whether they are complete, correct, sufficient, or permit the construction of illogical or flawed structures is not at issue. In fact, here we are trying to find just such a situation for the given rules. Also the underlying implementation of what the flowchart describes is not particularly relevant, even if we know how it's "really done" in real world implementations. By assuming the worst we can might be able to answer the question

The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads.

Yes, the results were merged, and to the user it appeared that nothing had happened except that the code ran faster. In actuality the threads ("microtasks") had come into existence previously and hung around in a sleep state waiting to be called into a fray. At the end of a given fray the results were merged via semaphore mechanisms and the tasks would depart, returning to a wait state ("spinwait"), and eventually to sleep if not promptly summoned for more work (yielding up the physical CPU for rescheduling by the OS), and await another summons to a fray. For microtasking and autotasking the underlying tasks weren't continually destroyed and recreated because the instantiation cost was too high (OS call, resource allocation, rescheduling). Much more efficient to do it once at the beginning of a program, or for a chunk where parallelism is going to be used, and have them ready to go either spin-waiting or at worst, waiting for the attaching of an available CPU.

But the implementation details are not what the user saw (or rather, what they weren't supposed to have to see...).

In the case of register access, register "scoreboarding" was used to indicate that a register was "waiting" for the output from some operation, suspending any operations wanting to use that register as input. I don't think there was any form of hardware "scoreboarding" for memory, so that required a software handshake (mutex, semaphore, ...).

No, no scoreboarding for memory, but there were shared registers and semaphore registers that could be used for managing memory based structures.

 

[sandy.bridge]

So essentially you have two threads running in synchronization, and then the third thread is evaluated after the first two are declared? Or are all three threads to be running in parallel and synchronized?

 

[rcgldr]

In this case we can only assume the rules are as given, no more, no less. Whether they are complete, correct, sufficient, or permit the construction of illogical or flawed structures is not at issue. In fact, here we are trying to find just such a situation for the given rules.

In that case, you could simply allow multiple threads to be running the same code with the same variables but out of sync and running at different speeds to create all sorts of problems. For example, take the pseudocode case

A: x = 0
B: x = 1
C: if(x == 1) then doclever

but with 3 separate threads running at the same time, thread 0 at A:, thread 1 at B:, and thread 2 at C:.

Normally a flow chart doesn't allow for the control point to be at multiple locations on the flow chart at the same time (due to the multiple threads). A flow chart normally represents the control flow for a single state machine, although it could be expanded to handle multiple threads, but there needs to be a reasonable convention for doing so.

However, the point is that you can bend the rules for pseudocode in the same way rules are bent for flowcharts to end up with the same issues.

Rcgldr: The threads weren't "merged", instead threads were terminated and the results pass on to other threads pending on the termination and output from those spawned threads.

For microtasking and autotasking the underlying tasks weren't continually destroyed and recreated because the instantiation cost was too high (OS call, resource allocation, rescheduling).

I only meant logically. The unused tasks would be in an idle / pending state when there was nothing for them to do. Also some of this out of order processing uses the equivalent of hardware multi-tasking that doesn't involve the OS, such as multiple arithemetic units on a single processor running at the same time, which the OS would be unaware of (the hardware would usually handle this with some form of scoreboarding).

 

[rcgldr]

So essentially you have two threads running in synchronization, and then the third thread is evaluated after the first two are declared? Or are all three threads to be running in parallel and synchronized?

You start with three threads running unsynchronized. The merging arrows would (or at least should) imply synchonization, with the middle thread waiting for both outer threads to terminate (or go idle as gneill pointed out), but in no specifc order (wouldn't matter which one terminated first). You could also invent other conventions for syncrhonization between threads.

Actually in a multi-threading environment, the ability to wait for multiple events with a single atomic call eliminates a lot of issues related to priority issues between the signaling and pending threads when the pending thread needs to wait for multiple events before continuing.

 

[sandy.bridge]

Is there a way to represent the "pending" of the middle thread to show that it is waiting for the side threads via flow chart? Or would I just have to have a brief explanation?

 

[rcgldr]

Is there a way to represent the "pending" of the middle thread to show that it is waiting for the side threads via flow chart? Or would I just have to have a brief explanation?

You could assume that it's implied by the merging arrows, but that would require a brief explanation. Otherwise, you need to create some convention for threads to signal or pend on events, in either your flowcharts or your pseudocode.

This still doesn't get back to the original problem, since there's no reason you can't "bend" the rules for pseudocode in the same manner as you do for flowcharts. I'm wondering what your professor's point is. Let us know when you find out.

 

[sandy.bridge]

Will do! Thanks for the help, guys.

 

[jedishrfu]

I think the point may be that recursion can be represented on a flowchart (tieing an if back to itself) whereas it can't be represented by psuedocode unless there's a provision for defining a method/function/subroutine in the pseudocode.

 

[rcgldr]

For multi-threaded applications, an alternative to flowcharts is a data flow chart, where blocks represent queues of element of data, and connectors represent the processes that retrieve an element from one queue, optionally perform some operation on the element, then append that element to another queue. Then for each process, you can use a conventional flow chart (with an operator to allow a process to wait for the presence of one or more elements on a queue).

 

[rcgldr]

I think the point may be that recursion can be represented on a flowchart (tieing an if back to itself) whereas it can't be represented by psuedocode unless there's a provision for defining a method/function/subroutine in the pseudocode.

How would you distinguish between iteration and recursion with a flow chart? In the case of flowcharts or pseudocode, there would need to be some convention to describe a recursive call (as opposed to creating what would appear to be a loop back to the start of the code).

 

[sandy.bridge]

Well, I emailed my professor and he essentially shot down all this work regarding this question. I do, however, have a hint: what implicit rules are there regarding performing the actions of a block, and is there a way to create a flow chart that violates one or more of these said rules.

Since blocks go from top to bottom in pseudo-code, what if we did something like this:

 

[rcgldr]

Well, I emailed my professor and he essentially shot down all this work regarding this question. I do, however, have a hint: what implicit rules are there regarding performing the actions of a block, and is there a way to create a flow chart that violates one or more of these said rules.

I would assume that the actions of a block are described as text within the block, and in that case why couldn't similar text be used in pseudocode?

If the point is that a single block could have multiple arrows going out of the block, you could duplicate this in pseudocode using a goto with an arrary of labels.

update - I just noticed your figure, but already covered this case, you just need an array of labels to use with a goto. In this case one label would go to "action2", the other would go directly back to "C1?" . Both are bending the rules in the same manner.

 

[sandy.bridge]

I'm starting to think that I am spending far too much time on this question.

 

[jedishrfu]

its probably going to turn out that the prof was mistaken or that there's some restriction he's not telling you about like a floating pt divide exception that causes a side-effect or that means you need another arrow into or out of the atomic action.

 

[rcgldr]

I'm starting to think that I am spending far too much time on this question.

I'd wait until the professor actually gives an example of a flowchart that can't be duplicated with pseudocode, assuming you're allowed to bend the rules in the same manner for both methods.

My bend the rules extension for goto syntax:

goto {label01, label02, label03, ... }

This could be interpreted as a random branch, or it could spawn multiple threads and branch to all the labels at once. If done in a loop, then it could be continously spawning multiple threads (will assume such a system has infinite resources).

 

[sandy.bridge]

Well, it's looking like I will just have to wait for the solutions. This was the last question on our assignment, but I may have to leave it empty.

"1. A block starts with a left curly brace { 2. All of the actions within a block are indented relative to its curly braces. This indenting is
consistent across the entire block.
3. A block ends with a right curly brace }
For example, the following is a block:
{
go to the front door
call out ‘‘trick-or-treat’’
}
You usually won’t just have a block by itself; blocks are a fundamental component of other
compound actions.
A block can contain any number of actions inside of it (including none at all!). In fact, a block
can contain other compound blocks inside of it. We’ll see that later.
A block has no special representation in terms of a flow chart. Blocks are used for disambiguation
in other kinds of compound actions; a flow chart has no ambiguities, since it always
uses explicit arrows to direct the flow to the next action."

This is what I have regarding blocks.

 

[sandy.bridge]

Since pseudo-code is supposed to evaluate each of its actions one at a time, what if we did the following? There is nothing in the flow chart that indicates which of the atomic actions it is supposed to evaluate first, and hence we would not be able to represent it in pseudo-code unless it was actually specified.

 

[jedishrfu]

Don't leave it empty put in your best guess, you may be right (maybe the prof is searching for the answer to the conundrum himself and waiting for that one special chosen student)

You can't win if you don't play.

 

[gneill]

Since pseudo-code is supposed to evaluate each of its actions one at a time, what if we did the following? There is nothing in the flow chart that indicates which of the atomic actions it is supposed to evaluate first, and hence we would not be able to represent it in pseudo-code unless it was actually specified.

I thought "bullets" could only have one arrow out?

 

[sandy.bridge]

Yeah, you're right.

 

[sandy.bridge]

In case you're interested, the solution was merely two flows meeting up at a bullet, and then going into an atomic action.

 

[gneill]

In case you're interested, the solution was merely two flows meeting up at a bullet, and then going into an atomic action.

But with only one START allowed, where does the second flow come from? That's what we were trying so hard to gimmick up with the phantom threads created by the dangling decision blocks... Hmph.

 

[rcgldr]

In case you're interested, the solution was merely two flows meeting up at a bullet, and then going into an atomic action.

Two flows or two paths, of which only one can be taken at a time? If it's two paths, then this is the same as pseudocode containing two or more branches to the same label.

 

[Joffan]

In case you're interested, the solution was merely two flows meeting up at a bullet, and then going into an atomic action.

Professorial fail. That's easy to represent in pseudocode and a common requirement.

I don't suppose you have a diagram of this so-called impossible flowchart.

 

[sandy.bridge]

Here:

 

[gneill]

But that's trivially implemented in any pseudo code that isn't deliberately hobbled by fanatical style rules.

 

[Joffan]

FirstTest: If not wantBanana then goto SecondTest
selectFruitFromBunch
Enjoy: peelAndEatFruit
goto FirstTest
SecondTest: if wantOrange then goto Enjoy
Stop