Why doesn't parallelism necessarily imply non-determinism?
The book is using the term non-deterministic in two different ways.  In concurrent computations and parallel computations the order in which the computations occur is non-deterministic.  The final result however may (or may not) be deterministic.

Consider the following example:

thread A        thread B
--------        --------
x = 0           y = 1


The x assignment might happen before the y assignment, or the y assignment might happen before the x assignment, so the order is non-deterministic, but the end result after both threads finish is that x contains the value 0 and y contains the value 1.  So the result is deterministic.

The two major ways in which we achieve deterministic results from non-deterministic ordering is (a) by performing completely independent computations in different threads and (b) by taking advantage of operations that are commutative and/or associative.  An example of case (b) is if you have an atomic addition operator:

thread A               thread B
--------               --------
atomic_increment(x)    atomic_increment(x)


At the end of the computation x will have a value 2 larger than it had before the computation, no matter whether thread A's increment happened before thread B's increment, or the other way around.