Register to reply

Converting flowchart to pseudocode

by sandy.bridge
Tags: converting, flowchart, pseudocode
Share this thread:
gneill
#37
Jan17-13, 08:40 PM
Mentor
P: 11,689
Quote Quote by sandy.bridge View Post
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
#38
Jan17-13, 09:06 PM
HW Helper
P: 7,132
Quote Quote by sandy.bridge View Post
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
#39
Jan18-13, 10:04 AM
P: 778
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
#40
Jan18-13, 10:29 AM
Mentor
P: 11,689
Quote Quote by rcgldr View Post
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
#41
Jan18-13, 11:09 AM
HW Helper
P: 7,132
Quote Quote by sandy.bridge View Post
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).

Quote Quote by gneill View Post
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
#42
Jan18-13, 11:29 AM
P: 778
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
#43
Jan18-13, 11:53 AM
HW Helper
P: 7,132
Quote Quote by sandy.bridge View Post
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
#44
Jan18-13, 12:01 PM
Mentor
P: 11,689
Quote Quote by rcgldr View Post
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
[quote]
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.
[quote]
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
#45
Jan18-13, 12:14 PM
P: 778
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
#46
Jan18-13, 12:15 PM
HW Helper
P: 7,132
Quote Quote by gneill View Post
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.

Quote Quote by rcgldr
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.
Quote Quote by gneill View Post
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
#47
Jan18-13, 12:17 PM
HW Helper
P: 7,132
Quote Quote by sandy.bridge View Post
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
#48
Jan18-13, 12:22 PM
P: 778
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
#49
Jan18-13, 12:30 PM
HW Helper
P: 7,132
Quote Quote by sandy.bridge View Post
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
#50
Jan18-13, 12:31 PM
P: 778
Will do! Thanks for the help, guys.
jedishrfu
#51
Jan18-13, 12:36 PM
P: 3,000
I think the point may be that recursion can be represented on a flowchart (tieing an if back to itself) whereas it cant be represented by psuedocode unless there's a provision for defining a method/function/subroutine in the pseudocode.
rcgldr
#52
Jan18-13, 12:37 PM
HW Helper
P: 7,132
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
#53
Jan18-13, 12:39 PM
HW Helper
P: 7,132
Quote Quote by jedishrfu View Post
I think the point may be that recursion can be represented on a flowchart (tieing an if back to itself) whereas it cant 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
#54
Jan18-13, 12:53 PM
P: 778
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:
Attached Thumbnails
unnamed7.png  


Register to reply

Related Discussions
Logarithm flowchart Engineering, Comp Sci, & Technology Homework 3
Drawing a flowchart Engineering, Comp Sci, & Technology Homework 4
All encompasing mathematics flowchart General Math 8
Flowchart HElp Introductory Physics Homework 4