What does actually 'program order' mean?

Question

AFAIK Leslie Lamport has stated the following:

... the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

Taken from: Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.

So, I'm wondering whether that implies a high-level language program, like C, assembler text after compiler optimizations or rather a trace of instructions in a processor after out-of-order scheduling?

Bk

Answer 1

Generally this phrase means, "the sequence of (machine) instructions as listed in order in the program, following branches in the obvious way". In particular, it is intended to describe the "simple" model of the program, as a reference; it is NOT intended to talk about the program after optimized execution.

I've not seen it applied to higher level programs, but then this isn't my exactly my technical turf. There are similar concepts for C and other derivative langauges, called "sequence points". These indicate which parts of the program must have have been completed by the sequence point. This gives you what amounts to the partial order equivalent of "program order".

Carmelcarmela