Subject: [rohc] optimal length udvm assembler - NP complete?

From: Cristian CONSTANTIN <[email-masked]>
Date: Wed, 8 Jun 2005 17:11:18 +0200

hi!

this e-mail contains references and examples adapted from the paper:

 Thomas G. Szymanski, Assembling code for machines with span-dependent
 instructions, Communications of the ACM, v.21 n.4, p.300-308, April
 1978

you'll maybe need to have a look before reading on...

it seems to be a known fact that assembling code for a machine with
"span-dependent" instructions, in its most general form (i.e arbitrary
complex assembly-time label expressions) is an NP-complete problem.
is it also the case for the udvm (the virtual machine specification in the
sigcomp rfc) and its assembly language specified in
draft-ietf-rohc-sigcomp-user-guide-01.txt ?

there is a proof in the paper mentioned above that the problem of
generating optimal length code is NP-complete when the span dependent
instruction are pathological. I have tried to adapt the example
containing a pathological instruction from the page 303 to udvm; here is
what I came up with:

X: pad(65404)
Y: JUMP(someplace)
Z: JUMP(X) 

my calculations (under the assumption that a short operand is
represented on 1 byte and a long one on 2 bytes) lead to the following:

empty_span(Z)=129, so we must use a long representation under the empty
span assumption

full_span(Z)=128, so we could use a short form representation under the
full span assumption

that leads to the conclusion that Z is pathological; code containing
sequences like this would render the optimal assembler into an
NP-problem. if my example and my calculations are correct, it is even 
worse than the PDP-11 type of problem from the paper because there 
_no_ pathological instructions with simple labels can appear.
(PDP-11 instr. could be pathological _only_ when using labels of the form 
"L+constant" or "L-constant" with constant!=0)

but then again, my calculations/example can be wrong, everything
I have said becomes rubbish and the question whether this is NP-complete
or not will be still open; or does anyone know the answer? :-)

bye now!
cristian
-- 
 _          | There are many people who use UNIX or Linux  
(_'_        | who IMHO do not understand UNIX.
  (_'rist   |              --David Korn  
GPG public key at wwwkeys.de.pgp.net
_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 8 Jun 2005 17:28:17 +0200

On Jun 08 2005, at 17:11 Uhr, Cristian CONSTANTIN wrote:

> does anyone know the answer

Well, even though the researcher in me would like to know the answer, I 
don't really care, because it is very easy to write an assembler that 
will generate good enough code.
I think this is one instance of the set of optimization problems where 
finding the truly optimal solution in all cases may be hard but it is 
extremely easy to get within 0.1 % for real-world problems.

Gruesse, Carsten