select, nondeterminism and deterministic properties

Technical questions regarding the XTC tools and programming with XMOS.
User avatar
Respected Member
Posts: 450
Joined: Wed Apr 25, 2012 8:52 pm

select, nondeterminism and deterministic properties

Post by aclassifier »

This is rather messy, but it reflects my state of understanding..

I need to understand the fairness [2] and nondeterministic nature of the select [1] (really?) with the deterministic properties of XC code (also [1]).

In [1] I wrote:
XMOS states, while describing an example (page 23 of [5]) that: “If both inputs become ready at the same time, only one is selected, the other remaining ready on the next iteration of the loop.”
Page 47 of [6] states it differently: “If more than one of these inputs or transactions is ready then the choice of which is executed is made nondeterministically.”
The first quote takes “the other” and “next iteration” into account. This is interesting, if there is a concern of “fairness” in it. ..
The XMOS XCore processors have “deterministic thread execution”, as they write in the introducery texts about them. Or “up to 8 concurrent, deterministic real-time tasks”.
Nondeterministic elements in the language and deterministic execution by the processor. ..
There also is this quote in the Ordering [[ordered]] chapter of [3]:
Generally there is no priority on the events in a select. If more than one event is ready when the select executes, the chosen event is unspecified.
Is "unspecified" in this as it says or is it nondeterministic == fair? As in the occam, PRI ALT an [[ordered]] select would be a way to let the programmer build his own interpretation of fairness.

There also of coure is the case of good and bad nondeterminsm. From [1]:
I did get a letter from a computer scientist and author the other day, stating this:

“I tend to say the functional correctness of a program should not depend on the choice made where there is a non-deterministic choice – but the temporal correctness of a program may.”

“..if you could show that any choice leads to temporal correctness then that would be fine. I tend to stress that determinism is not necessary – what we need is predictability.
Of course one way to get predictability is to be deterministic, but this is not the only way”
Could anybody help me getting (some of) this straigth? (That would include saying against the quotes of my own writing etc.) I am hoping to tell about it with somewhat more certainty in an invited lecture at the real-time course at NTNU (in Trondheim) next week..

- - -
[1] Nondeterminsm chapter "XC by XMOS". This chapter is quite complex, and I am not certain if I got all of it right..
[2] XC code examples chapter "XC server with state-based timing serving two clients". This code certainly behaves fair where a server handles clients equally "often", with no magic code to ensure it. It's just another example of the very elegant XC
[3] XMOS Programming Guide (as of 17Jan2018: 2015/9/21 version F, 2015/9/18 in the document), see
- - -
[5] is in [1]: ... 1009A).pdf
[6] is in [1]: ... [Y-M]).pdf

Øyvind Teig
Trondheim (Norway)