Browse Prior Art Database

Storage Compression for Indirect Threaded CODE Machines

IP.com Disclosure Number: IPCOM000041488D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 4 page(s) / 89K

Publishing Venue

IBM

Related People

Garyet, DC: AUTHOR [+2]

Abstract

Described is a method for compressing the address thread of an indirect threaded code language by keeping a table of the most commonly used addresses and referring to those addresses in the thread by a single-byte index into the table. The single-byte table indices are distinguished from double-byte direct address references by the state of their low-order bit. (The low-order bit is preferred for a status bit because frequently, in a 16-bit word machine, the direct address reference must be aligned on a 16-bit boundary, requiring the low-order bit to be zero for those references.) Indirect threaded code machines, of which the most popular are those based on the language FORTH, employ a new technology for implementing microcode which may possibly become a preferred technology.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 4

Storage Compression for Indirect Threaded CODE Machines

Described is a method for compressing the address thread of an indirect threaded code language by keeping a table of the most commonly used addresses and referring to those addresses in the thread by a single-byte index into the table. The single-byte table indices are distinguished from double-byte direct address references by the state of their low-order bit. (The low-order bit is preferred for a status bit because frequently, in a 16-bit word machine, the direct address reference must be aligned on a 16-bit boundary, requiring the low-order bit to be zero for those references.) Indirect threaded code machines, of which the most popular are those based on the language FORTH, employ a new technology for implementing microcode which may possibly become a preferred technology. In an indirect threaded code machine, control logic is represented as a "thread" of addresses which point to memory locations which contain addresses pointing to actual machine instructions. The described scheme compresses this thread of addresses so that it occupies significantly less memory than the addresses conventionally would. In one large FORTH nucleus system, 31% less memory was required for the program. The following terms, used in the description of the compression scheme, are defined for clarity of description. DICTIONARY is a section of memory containing the words (command structures) defined in the FORTH system. There is a dictionary entry for each word. The entry describes the address thread to be executed when the word is invoked. The format of the entry is illustrated in Fig. 1, and its fields are described below. The NAME FIELD contains the name of the word. The NFA (Name Field Address) is the address of the first byte of the Name Field. The LINK FIELD is a word which contains the NFA of t he previously defined word in the same context. LFA (Link Field Address) is the address of the link field. A CODE POINTER is the address of an assembly-language routine. CFA (Code Field Address) is the address of a word which contains a code pointer. The PARAMETER FIELD is the list of opcodes and data which define the address thread of a particular word. PFA (Parameter Field Address) is the address of the first byte in the parameter field. OPCODE is herein defined as an entry in the parameter field which refers to a CFA. This entry may be 1 or 2 bytes long. (In standard FORTH, opcodes are CFA's and are always 2 bytes.) The conventional execution scheme of FORTH is illustrated in Fig. 2, which uses, as an example, a typical user-defined word, TRAVEL, using previously defined words. The execution of the word GET-TICKET is initiated by obtaining its two-byte CFA address directly from the parameter field of TRAVEL. Code compression is achieved, at the expense of performance, by adding another level of indirect addressing to the interpreter and storing the most-used CFA's in a 256-byte "token table." A two-...