View unanswered posts | View active topics It is currently Sat Feb 17, 2018 7:13 pm



Reply to topic  [ 11 posts ] 
 CPU/VM design.code optimization & data compression algorithm 
Author Message

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
Hi everyone! I would like to share some infos and ask questions. I have questions about how to optimize the machine code for this BitBitJumpJump CPU design. How to produce equivalent-behaving code that is shorter? The CPU has this behavior:

Code:
instruction=0
while running:
  field0,field1,field2,field3=instructions[instruction]
  data=read(field1) //read input data from an address that maps to memory or input port
  write(data, field0) //write data to the output address (memory or output port)
  instruction=selector?field3:field2 //use a selector bit to select the next instruction


Every instruction has 2 data addresses (from where to read and where to write) and 2 instruction addresses (next instruction for case 0 or case 1 of value of selector bit).
I want to use this machine design for a data compression challenge, as a virtual machine, but in this case reducing program size is very crucial. That would mean producing the shortest program that outputs a given string of bits, a given file. I may ask for this performance to specialists such as Toptal, but first I would like to discuss it more. The designs and ideas are given under 2 clauses: Attribution of the ideas in case of reproduction or derivative works. No liability nor guarantee of fitness for a particular purpose.
https://jsfiddle.net/devdev/og526zfw/4/
The idea has been stimulated by the NOR machine (https://pragprog.com/magazines/2012-03/the-nor-machine) and Hutter Prize Data Compression Challenge (http://prize.hutter1.net/).


Fri Jan 13, 2017 2:12 pm
Profile

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 870
Welcome, and thanks for bringing the discussion here.

I'll note that you mentioned your instruction set over on the Esoteric Languages wiki.

(Whereas BitBitJump reads and writes bit-addressable memory, with aligned blocks of bits being accessed for the instruction stream, it's ambiguous to me whether or not your machine uses word-addressed memory. As you observe, BBJ normally has to bit-flip future instructions in order to construct conditional flow, whereas you have a single privileged bit which you can flip to affect the next instruction (and subsequent ones, until you flip it again.)

It seems to be a feature of single-instruction machines that their programs will generally be rather long - so perhaps it's not surprising you'd like to make them shorter! It's not obvious to me how this makes for an efficient data-compression tactic.


Fri Jan 13, 2017 3:47 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
Well... let's try! :)

https://sites.google.com/site/dariocangialosi/microcode-microptimizations-a-vm-as-a-possible-part-of-solution-of-a-compression-challenge

The "BBJJ Compression Challenge" as formulated by Dario Cangialosi (me):
Produce the shortest BBJJ program that produces the enwik8 bitstream from the Hutter Prize challenge.

I have not a definitive answer yet. I have to say that the "question answering" microcode could be compressed also (I have asked myself questions on the efficiency of the representation), also by means of self-modifying programs (and/or just trying to "zip compress" the microcode could made some efficiency gain in terms of size efficiency.)


Fri Jan 13, 2017 4:20 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
Quote:
you have a single privileged bit which you can flip to affect the next instruction (and subsequent ones, until you flip it again.)

Yes, you got it correctly, this how my BitBitJumpJump implementation works, it is a privileged (write-addressable) bit.
It is read when choosing the next instruction among the 2 addressed in the (current) instruction.

The format is very "verbose" so further care to compress the program has to be taken. But I think that this is an interesting way to see the data compression-by-program problem. By producing a very very optimized program, a micro-optimized program.

Another strategy would be to produce again x86 code or similar, in order to have a maybe more efficient program representation (after the program has been size-optimized with the BBJJ "LowLevel VM" strategy).


Fri Jan 13, 2017 4:29 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
In other words I am seeking "ultimate bit-level program optimization" and this goal can serve for "ultimate bit-level data compression" (one leads to the other).


Fri Jan 13, 2017 4:53 pm
Profile

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 870
From your site:
Quote:
This is a BBJJ (BitBitJumpJump) program runner with example programs:
https://jsfiddle.net/devdev/og526zfw/4/


Nice use of jsfiddle! You can show your code, and have the code running in the browser, and indeed people can fiddle with it. You could even have some self-documentation in the HTML, like easy6502 does.

Quote:
In other words I am seeking "ultimate bit-level program optimization" and this goal can serve for "ultimate bit-level data compression" (one leads to the other).

Well, for best compression it makes sense to have well-optimised code - but not necessarily optimised for size. The interesting thing about this challenge is that you're compressing 100MByte and your metric is the size of the program+data. And yet, with such a large data corpus, for a conventional approach, the size of the program is not a big impact on the result. Compare that with, say, producing a compressed 32k ROM, where the size of the decompression header program might be a substantial fraction of the total if you were not careful.


Fri Jan 13, 2017 5:00 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
I might say sound controversial but in the Hutter Prize approach to data compression you can have a program-only solution, that includes all the needed data and behavior to produce the target enwik8 bit-stream. Note that even in my BitBitJumpJump implementation you could hard-code data, fixed bits, and express them as program (and not as program's attachment of data). So for me the program includes all. And given that the program format has a fixed size for instruction binary format (I implemented binary program representation in C and Python implementations), then the only thing that counts in terms of size would be the number of instructions. Then we could think also to compress the programs and see which program is better compressed (by more classical means also).


Fri Jan 13, 2017 5:13 pm
Profile

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 870
Indeed, I thought you were heading in that direction.

It's not obvious to me that all-program is a better tactic. But it might be interesting to see where the idea takes you.


Fri Jan 13, 2017 5:18 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
A way to reduce the program size could be to use relative addressing in jumps (specifying an address relative to the current instruction address, and not absolute addressing, i.e. relative to the beginning). This can make quite a difference in big programs where addresses can become big numbers. It would also depend on code "locality" (how the code of an instruction is localized, e.g. far or near the current one).


Fri Jan 13, 2017 5:55 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
On the "address locality" I have pondered to use Grey-code based addresses, for addresses that change only in one bit, like the Grey-code when counting. For example storing the address of the changed bit, not the whole address. That would mean, for example, instead of using a nibble (4 bits) for 2^4 addresses (16 addresses) it would mean 16 bits for each address (only 1 of them is changed). that is 2^16 addresses (65535).

Also I am considering of running several sub-programs in sequence to form the target data. That would be a way to produce more data using the same program format (using more than 1 program per file, many sub-programs whose output is e.g. concatenated). That would both circumvent program format limitations and would allow to subdivide the problem in sub-problems (making it less unwieldy to reason and to compute about).


Fri Jan 13, 2017 6:12 pm
Profile

Joined: Tue Jan 10, 2017 6:42 pm
Posts: 9
Furthermore, there are ways (more than one way) to make the program bits and data bits one and the same (i.e. having writable programs, self-modifiable programs). In these cases the duality of program vs data is lessened to the point that the previous discourses are to be seen in a different way. Maybe there would not be the necessity to choose once and for all the approach (more data-oriented vs more program-oriented).


Fri Jan 13, 2017 7:47 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 11 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software