music
music |
 | OSdata.com |
This web page discusses a possibility for RISC machines. This feature does not exist in real hardware.
I propose a composite data type. Currently RISC (and most CISC) processors directly support the use of scalar data and addresses. CISC processors often have address modes that are designed for certain kinds of composite data. The autoicrement and decrement used for stacks and some kinds of queues still exist in RISCs.
I suggest two or three new isntructions.
One instruction tells the processor that we want a particular register set up as a window into a certain kind of composite data structure (array, list, tree, stack, queue, etc.). The scalar data of the first item in the composite data structure appears in the designated register.
A second instruction informs the hardware to optionally write any changes to the existing item in the register and then step forward or backward (left/right, up/down, etc.) to the next scalar data item in the data structure. The hardware can use caches and prediction circuits to make sure that the next scalar data is ready for fast use.
Because the address register is hidden away in the hardware, we free up one more valuable register in our register set. Old method requires two visible registers, one for the address and one for the scalar data. We also gain speed increase by removing explicit address computations from the program.
A third instruction (or an option on the second instruction) places the current address in the composite data structure into the visible register. The program can now take explicit control for insert and delete operations. Modify operations are handled by the second instruction.
At the cost of two (or three) additional instructions and some hidden additional hardware, we gain much better control over composite data types without weighing a RISC down with lots of address modes or bunches of additional specialty instructions.
free computer programming text book projectIf you like the idea of this project, |
This web page discusses composite registers as a possibility for RISC machines. This feature does not exist in real hardware.
In general, computer registers contain scalar data.
RISC machines rely on a large number of registers (scalar) and a load/store architecture with a small number of addressing modes.
Most of the composite data types have been around for decades and their characteristics are well known.
Some of the common composite data types include arrays, strings, text blobs, stacks, queues, lists (single and double linked), trees, and graphs.
These composite data types are going to appear repeatedly through programs.
I propose that it would be useful to have hardware support for composite data registers.
To be technically complete, I will point out that there are examples of hardware support for composite data types.
Almost every computer (including RISCs) since the 1960s has included hardware support for stacks (in the form of pre-/post- increment/decrement). Many CISC processors (including all three of the major 16-bit microprocessors) include an addressing mode to support arrays. The VAX from the 1970s included hardware support for queues and a number of different specialized kinds of tables. Many of the advanced addresing modes of CISC machines had some kind of composite data use.
As my example, consider a character match search of a string. The string is normally too big to fit into a single scalar register. Normally the string is stored in cosecutive memory locations and a register is used as a pointer to the beginning of the string and then incremented to step through the string.
In a typical RISC this involves two registers. One register holds the pointer to the memory address of a portion of the string and another register that holds the scalar data of a character or a small set of characters. We check the scalar sample (in this example, comparing for a character match). Then we increment (or decrement) the addres pointer register and load the next sample. The process repeats until the end of the string or a successful character match.
Now imagine that we used hardware support for this operation. We have a single instruction to initialize what we will be doing. Inputs would include the starting address of the string and an indication that we want to view the subsequent series of bytes as a character string and the method for determining the end of the string (such as a count byte such as in Pascal or a ending zero byte such as in C) and a method of use and the designated composite data register.
The hardware (hopefully making strategic use of the processor’s caches) will fetch a character or small group of characters and load them into the composite data register. In our example we will perform some compares and decide that we have obtained a match or determine that we need to continue our search with the next character or group of characters. Eventually we may reach the end of the string and a final conclusion on match or no match.
We need a method of use and a corresponding method for determining when to load the next part of the string. One obvious method is to read the slice of the string into another register and the reading will initiate the fetch and load of the next part of the string. This method wastes the register we freed up by getting rid of the separate address register.
Another method is a second special instruction. We leave the data in the composite register and do whatever examination or manipulations or transformations desired. The special instruction can indicate the need to fetch the next portion of the composite data type. The special instruciton can indicate whether we want the scalar data to be written back into memory. The special instruction can even carry the information on the data type and handle the appropriate different memory calculations for different composite data types.
Stepping through an entire array is similar to stepping through a string or text blob, except there may be gaps to force alignment.
Linked lists can be viewed as having a data portion and a pointer portion, each of a fixed size. If the hardware knows the sizes of the two portions and how they are intermingled, then it can use the address portion (pointer) to locate the next part of the composite data structure. The hardware can use the processor caches to prefetch large portions fo the linked list for more efficient RISC processing. This can also be used for doubly linked lists.
The same princple applies to trees, with the additional complication of alternate paths.
In the case of certain kinds of tree trversals, the enitre path is predictable in advance and we can have an efficient hardware algorithm for prefetching all of the data.
But in other cases, we are making decisions on which path we use to travel the tree (such a binary search of a balanced B-tree). In this case, we need to provide the information on the desired pathway in our special instruction for the next fetch. Also, the predictive circuits face many of the same problems as the predictive circuits for decisions in object code.
A third instruction (or an option on the second instruction) would be used to get the actual address of the current part of the composite data being examined. This allows us to switch to programmer control of the composite data structure, which can be used for operatiosn such as delete and insert. Modifications can be handled with the second instruction (which would have read, write, and read/write modes).
Note that this proposed technology will have hidden registers holding addresses and possibly other information, so the circuit count for the processor goes up rather than going down.
The savings is in freeing up a still limited number of valuable registers. The address registers (and any other registers used to store additional information about the sturcture of the composite data) are moved to specialized hardware and those registers are now available for use as both normal scalar data registers and as our new proposed composite data registers.
We add only two (or possibly three) additional instructions to the instruction set ([1] an initializing instruction and [2] a next step instruction and [3] a fetch actual address instruction or option).
Ideally the entire operation is othogonal and any register can be used as either a scalar or composte register. And we can intermix the two kinds of operations on the exact same register (use the composite register approach to load some data, use the scalar register instructions to do some processing, and then fetch the next part of the composite data.
Note that this same approach can be used to support concurrent operations and parallel programming. Reductions and other concurrent operations will fit very neatly into this model.
Our new approach maintains all of the advantages of the RISC approach while adding back in capabilities previously handled by CISC’s many addressing modes. But we have a much more sophisticated hardware method than the old CISC address modes.
Programming example: I am making heavily documented and explained open source PHP/MySQL code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).
View music player in action: www.musicinpublic.com/.
Create your own copy from the original source code/ (presented for learning programming). Includes how to run this from your own computer if you don’t have a web site.
OSdata.com is used in more than 300 colleges and universities around the worldfree downloadable college text book on computer programming. |
return to table of contents
free downloadable college text book
Because I no longer have the computer and software to make PDFs, the book is available as an HTML file, which you can convert into a PDF.
| Tweets by @osdata |
A web site on dozens of operating systems simply can’t be maintained by one person. This is a cooperative effort. If you spot an error in fact, grammar, syntax, or spelling, or a broken link, or have additional information, commentary, or constructive criticism, please e-mail Milo. If you have any extra copies of docs, manuals, or other materials that can assist in accuracy and completeness, please send them to Milo, PO Box 1361, Tustin, CA, USA, 92781.
Click here for our privacy policy.
 |
 |
| previous page | next page |
free computer programming text book projectBuilding a free downloadable text book on computer programming for university, college, community college, and high school classes in computer programming. If you like the idea of this project, Supporting the entire project: If you have a business or organization that can support the entire cost of this project, please contact Pr Ntr Kmt (my church) free downloadable college text book on computer programming. |
I do the news as an unpaid volunteer for KOCI 101.5 FM, Newport Beach/Costa Mesa (also available on the web)
This web site handcrafted on Macintosh 
computers using Tom Bender’s Tex-Edit Plus 
and served using FreeBSD 
.
Names and logos of various OSs are trademarks of their respective owners.
Copyright © 2013 Milo
Created: June 5, 2013
Last Updated: June 5, 2013
return to table of contents
free downloadable college text book
|
|
| previous page | next page |
