Complexity of optimal vector code generation (Q807020)

A vector machine consists of a collection of processors (functional units) which execute operations on a collection of vector registers. There is a single instruction process unit which supplies instructions to the functional units. The sequence generated by the instruction process unit is called code sequence. The period in which the instruction process unit is blocked is called a \(chime\). A vector machine computes vector expressions which are expression trees specifying the chaining of the operations. The paper under review shows that the following problem is NP-complete: given a vector expression, find a code sequence with minimum number of chimes. The key of the proof consists in reducing the partition problem of a set of positive integers to the optimal code sequence problem.