beginners' 6502 articles in the works

[Dr Jefyll]

GARTHWILSON wrote:

Thanks. I had to resist the urge to answer Mr. nes's comment there and tell why the 65816 is way better than his 6809.

'kay, a minute ago I posted a plug for the cause.

[ChuckT]

You made the blog of Adafruit with a lovely picture.

http://www.adafruit.com/blog/2012/05/10 ... -computer/

[GARTHWILSON]

Nice. Now maybe I need to put something in the first page to get people to quit thinking of the 6502 as 1MHz NMOS!

[Dajgoro]

GARTHWILSON wrote:

Nice. Now maybe I need to put something in the first page to get people to quit thinking of the 6502 as 1MHz NMOS!

Pictures always works, especially if they are shot with good lightning, and if they show a good mess of wires... (at least it works for me) As for the 1mhz, my nmos 6502 works @4mhz, but it gets insanely hot(it is always hot anyway, but a bit more when clocked).
You could also shoot some sort of video tutorials, since people prefer to watch youtube videos, instead of reading. Or something just for the first page.

[GARTHWILSON]

GARTHWILSON wrote:

Now I'm working on the EPROMs for the big look-up tables for 16-bit math, the multiplication, inversion, log & trig functions, etc.. I can't believe I calculated the Intel Hex files 11 years ago! They've just been collecting dust all this time. [...] Of course as we all know, EPROMs are slow, but the plan is to also put the Intel Hex files on my website [...] so the reader can also have a way to load them into RAM from serial flash, or whatever. I will offer the programmed EPROMs too. If you want to do a lot of scaled-integer math, looking up answers, correct to all 16 bits (or in the case of inverses, all 32 bits!), will be extremely fast compared to actually calculating them.

It's done and ready for the corrections the initial readers will point out that I need to make before linking to it on my home page, links page, and broadcasting to Hackaday and other websites. There's a lot of explanation as to the usage, how the files were formed, very accurate rational-number approximations, how Intel Hex files work, etc.. It's at http://wilsonminesco.com/16bitMathTables/index.html . If all goes as planned, Tony will be programming the EPROMs for me to supply.

In the most dramatic cases, looking up a function from the tables will be nearly a thousand times as fast as actually calculating it (500MHz+ Apple II, anyone?), and it will be correct to all 16 bits.

[BigDumbDinosaur]

GARTHWILSON wrote:

It's done and ready for the corrections the initial readers will point out that I need to make before linking to it on my home page, links page, and broadcasting to Hackaday and other websites. There's a lot of explanation as to the usage, how the files were formed, very accurate rational-number approximations, how Intel Hex files work, etc.. It's at http://wilsonminesco.com/16bitMathTables/index.html . If all goes as planned, Tony will be programming the EPROMs for me to supply.

In the most dramatic cases, looking up a function from the tables will be nearly a thousand times as fast as actually calculating it (500MHz+ Apple II, anyone?), and it will be correct to all 16 bits.

• Ideas for interfacing:
  
  normal on-the-bus method: The easiest way is of course to just put the EPROMs on the bus, or load the files into RAM, if you have a processor with megabytes of address space like the 65816

A suggestion worth considering: since the computation data tables are (we hope) static, the EPROM user could consider burning the tables into OTP EPROMs, which typically boast a 45 ns access time. Such an EPROM would work in a 65C816 system running full tilt (20 MHz) with, at most, only one wait-state. I'm sure the user would be more than happy with the computation performance of such a system.

I don't particularly like the idea of interfacing a 65C22 to a 75xx545 shift register for accessing the data tables, which sounds cumbersome to implement and to program. I like the idea of windowing the appropriate ROM in and out of MPU address space as required. While there would be some overhead involved in decoding addresses and generating chip selects, the principle would be the same as mapping different pieces of SRAM into view. Sounds like a job tailor-made for glue logic in a CPLD. Just me and my $0.02 kicking in.

Incidentally, the ideal of scaled "floating point" as integers was used (more or less) in naval ballistic computers, since a real floating point number is, as you point out, somewhat slow and cumbersome to work with in systems without floating point hardware. I first learned about this math technique in the 1960s when I was attending electronics school in the Navy. They even had a tube-powered ballistic computer for us to play with. I "killed" a few whales with my first attempts at programming the beast.

[GARTHWILSON]

Quote:

A suggestion worth considering: since the computation data tables are (we hope) static, the EPROM user could consider burning the tables into OTP EPROMs, which typically boast a 45 ns access time. Such an EPROM would work in a 65C816 system running full tilt (20 MHz) with, at most, only one wait-state. I'm sure the user would be more than happy with the computation performance of such a system.

Tony apparently can program 27c801's and 27c080's with his Needham's EMP-10 programmer. I don't think those come in such fast versions, but I'm open to find out the fastest 1Mx8's that will be readily available for a long time and preferably have the same pinout. OTP generally just means there's no expensive UV window, but they have the same die which won't be any faster. I've seen 45ns EPROMs, but not in that density. If you know where to get them, please let us know. I looked into EEPROMs but couldn't find any that big IIRC.

As the code examples show, the speed penalty for putting the ROMs on parallel I/O ports is not major-- then you could run even 120ns EPROM at 20+MHz because the EPROM has a lot more than one cycle to respond.

Another possibility is to provide the tables in an SPI flash memory in an SO-8 (probably mounted to a DIP adapter) that the user can download into RAM. I can program that myself without making or buying an EPROM programmer. (My own commercially made programmers don't work for EPROMs that big.)

The serial method with the 595's is kind of a last resort, something you can do with a computer that's already built up and has all its parallel I/O taken. I'll add a note to that effect. [Edit: done.] The serial interface will still be much, much faster than actually calculating the values. Example code is provided. I guess I partly want to show that taking advantage of the tables does not require waiting until you can build your next computer.

[Nightmaretony]

I still like the serial as it allows a fairly massive amount of memory including scaling upwards without memory addressing costs. On my own pinball board, it does have a 4 meg upwards which is banked into an 8k page, along with paged ram if needed. To scale it upwards would requitre more lines out of the CPLD logic and I already have lines accounted for galore. Garth's method is literally infinitely scalable upwards.

[GARTHWILSON]

Nightmaretony wrote:

I still like the serial as it allows a fairly massive amount of memory including scaling upwards without memory addressing costs. On my own pinball board, it does have a 4 meg upwards which is banked into an 8k page, along with paged ram if needed. To scale it upwards would requitre more lines out of the CPLD logic and I already have lines accounted for galore. Garth's method is literally infinitely scalable upwards.

which is how I got hundreds of bits of 12-volt I/O for the automated production test equipment, 12V logic being needed to control 12V analog switches and drive 12V relays, especially since there were fewer IC choices on the market for that kind of thing at the time. There were only three lines to convert the logic levels on. The 5V parallel I/O on the computer board was used for LCD, keypad, printer, and a few other things. It was filled out, so there had to be another provision for the other hundreds of bits anyway. The serial sure made the connections between the various boards easier.

The part I added because of BDD's suggestion is underlined here:

Quote:

Synchronous-serial: Computer already built up? Not enough memory space? Parallel I/O already taken? Don't want to wait until you can build your next computer to incorporate the look-up tables? Serial is of course not the first choice for speed, but it may be your ticket to implement the tables, and it's still well over an order of magnitude faster (not to mention more accurate) than having to actually calculate the math functions on a 6502. It takes 16 clocks' time to shift each byte of address and data, and, although we use delays for some of it, the processor can be getting the next byte ready to go while the current one is being shifted.

So-- no more critique on the tables section of the website? Is it that there's very little interest, and if so, is it because it doesn't seem beliveable that it could be so useful, or because the idea is still just too foreign, or maybe that people don't read it at all because they automatically turn off at the thought of interfacing more than 64KB of anything on a 6502? Is it hard to read? Intimidating? I've made just a few minor additions and changes based on BDD's and private feedback, but I was hoping to get more feedback before making it public.

[ElEctric_EyE]

I'm definately interested in your tables Garth. Is hex straight binary? I was thinking of using them, maybe the SIN table, for doing circles in my graphics plotting routines using the 16-bit 65Org16. Things are so darn busy right now, I'm finding it difficult to spare even a few minutes a day on my projects!

[whartung]

GARTHWILSON wrote:

So-- no more critique on the tables section of the website? Is it that there's very little interest, and if so, is it because it doesn't seem beliveable that it could be so useful, or because the idea is still just too foreign, or maybe that people don't read it at all because they automatically turn off at the thought of interfacing more than 64KB of anything on a 6502? Is it hard to read? Intimidating? I've made just a few minor additions and changes based on BDD's and private feedback, but I was hoping to get more feedback before making it public.

I love the idea, I'm just not someone who can actually use this.

What's nice about it is that is (mostly) universal, and can be used on other processors. The idea of a serial, universal "co-processor" is novel too. I was thinking it might be useful in the robotics area, where a simple controller could leverage these functions for work perhaps with an arm or some other higher order math. But then it came to mind a question of whether they need 16bits of resolution or not. I simply don't know, perhaps a 8 bit resolution is adequate for most tasks of that nature.

But extending the concept, not simply to trig functions, but to any function -- memoizing the entire domain, that's also interesting. Again from a robotics standpoint, much of the physics can be pre-calculated with properly bracketed data, combined with the serial access piece, the most simple and slowest of controllers can make use of specialized, sophisticated maths.

[GARTHWILSON]

ElEctric_EyE wrote:

I'm definitely interested in your tables Garth. Is hex straight binary?

Intel Hex is a method of representing the binary data in a text file which has some error-detection built in. The method is described at http://wilsonminesco.com/16bitMathTables/IntelHex.html which is one of the pages in the group. It is commonly used by EPROM programmers, although there are other ones they use also, Motorola S-record probably competing with it for top spot. Although EPROM programmers will generally handle multiple file types, you can also convert from one type to another with a software called SRecord. I put this blurb in my main page on the files:

• • Since my Needham's EPROM programmer software seems to have a bug in it for large files (and Needham's is out of business), I went on a quick search and found SRecord 1.60. Initially I just wanted to confirm that my Intel Hex files were valid and error-free as far as Intel Hex goes; but this software also lets you transform EPROM file types, concatenate, split, etc.. Version 1.52 is in the Ubuntu (Linux) software center for one-click download and installation. Enter "EPROM" for a search term and it comes right up. SRecord is command-line-only, which initially made it confusing because I didn't see any new icons and couldn't find it under "Applications". The voluminous .pdf manual could stand to have better command-line examples, but you'll figure it out. Much of the manual is spent on telling about multitudes of file types you will never use, so there's not really that much that you have to read.

Quote:

I was thinking of using them, maybe the SIN table, for doing circles in my graphics plotting routines using the 16-bit 65Org16.

and of course you can use the SIN table to get COS & TAN too. For COS, you just add 90° to the input first, and for TAN, take both the SIN & the COS as a rational number. (Info like that, plus much more complete, is in the "math table files' descriptions" clickable link at the top.)

Quote:

What's nice about it is that is (mostly) universal, and can be used on other processors. The idea of a serial, universal "co-processor" is novel too. I was thinking it might be useful in the robotics area, where a simple controller could leverage these functions for work perhaps with an arm or some other higher order math.

Actually it's good for virtually any kind of machine control or automation. Although it's good for graphics, it might shine most in non-human I/O applications.

Quote:

But then it came to mind a question of whether they need 16 bits of resolution or not. I simply don't know; perhaps a 8-bit resolution is adequate for most tasks of that nature.

In that case you might read only the high 8 bits and not the low 8 bits of a cell, although it's there for other times when you want the whole thing. Graphics on a low-res display might be a good application for only using the top 8 bits.

Quote:

But extending the concept, not simply to trig functions, but to any function -- memoizing [memorizing?] the entire domain, that's also interesting.

If someone offers a way for others who don't have my setup to calculate their own tables and make the hex files, I would like to link to it in my articles. Hopefully it would be a non-intimidating way.

Quote:

Again from a robotics standpoint, much of the physics can be pre-calculated with properly bracketed data, combined with the serial access piece, the most simple and slowest of controllers can make use of specialized, sophisticated maths.

True. I didn't really think of that. For a lot fewer parts and less board space there's the floating-point serial coprocessor available at http://www.awce.com/pak1.htm (although their very first paragraph shows they are not acquainted with how to do scaled-integer math). However, they say their worst-case add time takes 55µs and worst-case divide instruction takes 190µs; so how much longer must one of the more-complex functions take?! The serial method I show with the look-up tables takes under 36µs for any 16-bit function, even the most complex, on a 10MHz 6502 making the serial connection through a 6522; and that's not quite optimized since I used an empty JSR-RTS for some delays to give time for bytes to shift in & out, which gave a little more delay than I needed. The fastest method I give with the memory directly on a 65816's bus takes 3.5µs at 10MHz, again even for the most complex 16-bit function. It's not quite an apples-to-apples comparison, but it's clear that you gain a big performance advantage when you avoid the overhead of floating-point and also go with the tables.

[whartung]

GARTHWILSON wrote:

Quote:

But extending the concept, not simply to trig functions, but to any function -- memoizing [memorizing?] the entire domain, that's also interesting.

Memoization is a classic technique, typically used in more dynamic languages with closures, where when a function is called, the result is stored in a table keyed by the arguments. Then, when the function is later invoked, it can search the table for the a pre-calculated result. If the result exists, it returns that, otherwise it calculates a new one, stores that in the table for next time, and then returns the value. It's popular in dynamic languages because it's easy to create a memoize function that can turn ANY function in to a memorized function.

The extra detail here also is that some functions may well need several inputs, but that doesn't mean the technique can't work -- you just as a developer may need to break it up in to component pieces, or use smaller domains of values. Anything you can cram in to a 16 bit key would work (2 8 bit, 1 10 bit + 1 6 bit, 3 5 bit values...).

Quote:

If someone offers a way for others who don't have my setup to calculate their own tables and make the hex files, I would like to link to it in my articles. Hopefully it would not be a non-intimidating way.

I imagine its reasonably straight forward. The game is converting your answers in to a 16 bit value, the rest is simple formatting.

[GARTHWILSON]

whartung wrote:

Memoization is [...]

It sounds like a kind of cache then.

Quote:

Quote:

If someone offers a way for others who don't have my setup to calculate their own tables and make the hex files, I would like to link to it in my articles. Hopefully it would not be a non-intimidating way.

Woops, that should say, "Hopefully it would be a non-intimidating way" (removing the word "not".)

[Tor]

GARTHWILSON wrote:

[..]The serial method I show with the look-up tables takes under 36µs for any 16-bit function, even the most complex, on a 10MHz 6502 making the serial connection through a 6522;[..]

Some decades ago I programmed a 6502 to track polar orbiting satellites by feeding pointing angles to the servo system which controlled the satellite dish. Calculating the pointing angles was done in advance, however it had to be done on a minicomputer and the data was then pre-fed to the 6502 processor (via RS-232) just before AOS (Acquisition Of Signal). After looking at the description and numbers you've provided I believe the calculations could easily have been done on the 6502 itself with that method, and in time (lots of satellites, little time between passes).

I became more familiar with look-up tables at a later point. Some years after the antenna control system I worked on a satellite data processing system where the (at that time much faster) minicomputer itself could not hope to process the data in time between orbits, even with the assistance of its separate FPS (Floating Point Systems) array processor. So we used about 70 megabytes of tables for all the sin/cos and other functions we needed. Look-up tables were used throughout the industry up to the early nineties, at least, for what with today's computers can easily be processed on-chip. The top shelf in my office still contains several old CCTs with look-up tables used for a diverse set of applications for different minicomputers, e.g. VAX.

What intrigues me about your variant of tables is how space-efficient it is, among other things. As indicated above the look-up tables we used on those minis was kind of a brute-force method, with no regards for size.. that seemed to be the way to do it, wherever it came from. I guess a lot of the size difference is because we didn't use scale-integer math, the tables all handled floating point directly and that's why they got so large. I guess.

-Tor