Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
General-purpose computing with VASYL
#1
I will go back to GEOS stuff soon, but last week I was occupied by a question: can you write and run any program using VASYL instruction set? Can I have a shader that will process bitmap for PBS?

In other words - is VASYL's instruction set Turing complete?

After a week I already know the answer: big fat YES and I have a proof for this: https://github.com/ytmytm/c64-beamracer-subleq

SUBLEQ is an esoteric (meaning: real, working, just not very practical) computer architecture that has only one instruction: SUBLEQ.

The only possible instruction for such CPU is "SUBtract and branch if Less-than or EQual to zero".


Code:
Mem[b] = Mem[b]-Mem[a]
if (Mem[b]<=0) then goto c

It turns out that this is all you need for general-purpose computing and it was proven that SUBLEQ is Turing complete. In fact, there are even more of these One-Instruction Set Computer architectures.

SUBLEQ seemed feasible for me to try with VASYL: we only have DECA/B and BRA for arithmetic and conditional jumps, but having two independent memory ports with configurable step after every read/write was very promising. Especially since the step can go both ways - positive and negative.

The Display List Virtual Machine goes through SUBLEQ instruction - four word-sized pointers and updates itself using both memory ports:
  • to setup loads into VREG_ADR0/1 when data is read/written or when we need to set starting point of a lookup table
  • to setup loads into VREG_STEP0/1 when we traverse lookup table to add numbers, negate them or read the sign
  • to load into VREG_ADR0 the address of the next instruction
Lookup tables are very easy: setup VREG_ADR and STEP and make two memory reads.

Arithmetic was a bit tricky. We need to know the result of b-a when we have a and b. So we use one lookup table to transform value a into -a and then second lookup table to find the result of 0+b+(-a).

Much bigger obstacle was the program counter implementation. First I wanted to use PORT0 exclusively for that, but it's not possible - there is no temporary register and I need both memory ports for lookups (read from PORT0, write into PORT1).
But how to preserve PORT0? We can't - there is no way to read anything from the registers. We can only read from memory.

The solution was to extend SUBLEQ programs to be fully linked with explicit addresses of targets for jump when result is negative or zero and also for the positive branch. Any examples for SUBLEQ that you can find in the Internet will have the positive jump pointing implicitly to the next instruction.

The VASYL SUBLEQ VM can process about 214 SUBLEQ instructions per frame, so the virtual SUBLEQ CPU runs at about 10.7kHz.

Almost whole bank 0 is available for program and data - about 62.5KB.

I'm not an experienced SUBLEQ programmer and all I have right now is a debug program that does simple calculations and modifies a value stored into $d020 while the VM is running.

To conclude: yes, I have proven that VASYL ISA is Turing complete and you can port any program to it, at least indirectly through SUBLEQ.

This just opens the gate for flood of software running natively on VASYL: quasi-assembly language, Forth, shaders and even BrainFuck Smile

Thank you guys for VBASIC, without VLIST and VPEEK it would be very hard to debug this.
Reply
#2
This is a very impressive work. I am still reviewing it, but I already admire the vision, scope, and programming tricks used in the code. Frankly, this is something we had hoped for while creating VASYL's peculiar architecture - people showing up and creatively bending it in some unexpected ways. And boy, is this one unexpected! Smile

Our original plan was to gradually release some building blocks that can be used for more general programming, including routines implementing 16-bit counters, stacks, maps, etc. Sadly, the response of the C64 programming community was somewhat more muted than we expected, and what was to be an area of active exploration remains so far deserted. Thus I am even more glad that when the action finally happens, it is of this caliber.


One quick comment on preserving the contents of a port's ADR registers - it can be done, although it will cost you a bank and then some. The other port's ADRs will be clobbered, too (at least this is what I managed to come up with today, perhaps it can be improved). I will put up a repo shortly and post a link here.

I hope to have more to say after playing with the code tomorrow.

Once again, thank you and congrats on a cool project!
Reply
#3
Here it is. I added some commentary to explain what's going on - I hope it's clear enough. Build and link as usual, run, then stop the display list and examine the very first two bytes of VASYL's memory - they will contain the preserved contents of ADR1.

https://github.com/laubzega/beamracer-saveport

Not sure if this helps with the SUBLEQ PC issue, but the demonstrated tricks may be handy for other things.
Reply
#4
More lookup tables, clever! Yes, I think it will help. Also you reminded my about second DL that may be useful for special purposes, like signaling to C64 (e.g. via IRQ) that program has finished.

I have also realized that for simplified C (from http://mazonka.com/subleq/hsq.html ) I need to extend this code to 16-bit subtraction.
Reply
#5
Yeah, efficient signalling to the 6502 is key if we want to have reasonably fast IO.

In the meantime, I submitted a PR with PAL/NTSC autodetection (214 instructions is way too many for our puny US screens Wink) and some other minor tweaks.
Reply
#6
My friend has actually already said more than I probably would about how much of a positive surprise this actually is! Hats off for this out-of-the-crate idea!! ("box" would be too much inside-the-box to fit here ;-)
Reply
#7
I have submitted a PR that adds character output. It also demonstrates how to implement comparisons and efficient 6510/VASYL synchronization.

The tricks I had to use to ensure that synchronization works across frames on both PAL and NTSC made me think that an operating mode where display list DOES NOT get restarted at frame's start could be handy. Opinions? (whether it can be squeezed into the CPLD is another matter).
Reply
#8
There is now an experimental (i.e. messy) support for keyboard input in the "input" branch of my fork (https://github.com/laubzega/c64-beamrace...tree/input). I'll try to clean it up and make a PR once I catch some z's.
Reply


Forum Jump:


Users browsing this thread: 13 Guest(s)