LC-3
Encyclopedia
Little Computer 3, or LC-3, is a type of computer educational programming language
, an assembly language
, which is a type of low-level programming language
. It features a relatively simple instruction set, but can be used to write moderately complex assembly programs, and is a theoretically viable target for a C
compiler
. The language is less complex than x86 assembly but has many features similar to those in more complex languages. These features make it useful for beginning instruction, so it is most often used to teach fundamentals of programming and computer architecture to computer science
and computer engineering
students.
The LC-3 was developed by Yale N. Patt
at the University of Texas at Austin
and Sanjay J. Patel at the University of Illinois at Urbana-Champaign
. Their specification of the instruction set, the overall architecture of the LC-3, and a hardware implementation can be found in the second edition of their textbook. Courses based on the LC-3 and Patt and Patel's book are offered in many computer engineering and computer science departments.
Instructions are 16 bits wide and have 4-bit opcode
s. The instruction set defines instructions for fifteen of the sixteen possible opcodes, though some instructions have more than one mode of operation. Individual instructions' execution is regulated by a state machine
implemented with a control ROM
and microsequencing unit.
The architecture supports the use of a keyboard and monitor to regulate input and output; this support is provided through memory mapped I/O abstractions. In simulation, these registers can be accessed directly, and the architectural specification describes their contents. Higher-level I/O support is also provided through the use of the TRAP instruction and a basic operating system. The operating system provides functions to read and echo characters from the keyboard, print individual characters to the monitor, print entire strings in both packed and unpacked forms, and halt the machine.
All data in the LC-3 is assumed to be stored in a two's complement
representation; there is no separate support for unsigned arithmetic. The I/O devices operate on ASCII
characters. The LC-3 has no native support for floating-point numbers.
The hardware implementation given in the Patt and Patel text is not pipelined or otherwise optimized, but it is certainly possible to create a fast implementation using more advanced concepts in computer architecture.
Arithmetic instructions available include addition, bitwise AND, and bitwise NOT, with the first two of these able to use both registers and sign-extended immediate values as operands. These operations are sufficient to implement a number of basic arithmetic operations, including subtraction (by negating values) and bitwise left shift (by using the addition instruction to multiply values by two). The LC-3 can also implement any bitwise logical function, because NOT and AND together are logically complete.
Memory accesses can be performed by computing addresses based on the current value of the program counter
(PC) or a register in the register file; additionally, the LC-3 provides indirect loads and stores, which use a piece of data in memory as an address to load data from or store data to. Values in memory must be brought into the register file before they can be used as part of an arithmetic or logical operation.
The LC-3 provides both conditional and unconditional control flow instructions. Conditional branches are based on the arithmetic sign (negative, zero, or positive) of the last piece of data written into the register file. Unconditional branches may move execution to a location given by a register value or a PC-relative offset. Three instructions (JSR, JSRR, and TRAP) support the notion of subroutine calls by storing the address of the code calling the subroutine into a register before changing the value of the program counter. The LC-3 does not support the direct arithmetic comparison of two values; comparing two register values arithmetically requires subtracting one from the other and evaluating the result.
and dynamic memory allocation. In this model, four of the processor's eight general purpose registers take on special roles: R4 is used as a base register for loading and storing global data, R5 is used to point to the current function's area on the call stack, and R6 is used as a stack pointer. Additionally, R7 is usually reserved for storage of return addresses from function calls; the JSR, JSRR, and TRAP instructions automatically store return addresses in this register during their execution.
When a C function is called under this model, the function's parameters are pushed onto the stack right to left. Space is then made on the stack for the return value of the function being called, the address of the instruction in the caller to return to, and the caller's value of R5. Local variables in the function being called are pushed onto the stack in the order that they are declared. Note that the LC-3 does not have native PUSH and POP instructions, so addition and memory storage instructions must be used separately to implement the stack.
These changes make the hardware of the LC-3b slightly more complex than that of the LC-3. For example, the LC-3b needs a shifter (the LC-3 does not) and extra logic in its memory unit to properly handle loading and storing data of various sizes.
Ashley Wise maintains a set of tools for simulating and working with the LC-3b.
Educational programming language
An educational programming language is a programming language that is designed primarily as a learning instrument and not so much as a tool for writing programs for real-world work.-Learning paths:...
, an assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
, which is a type of low-level programming language
Low-level programming language
In computer science, a low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture. Generally this refers to either machine code or assembly language...
. It features a relatively simple instruction set, but can be used to write moderately complex assembly programs, and is a theoretically viable target for a C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
. The language is less complex than x86 assembly but has many features similar to those in more complex languages. These features make it useful for beginning instruction, so it is most often used to teach fundamentals of programming and computer architecture to computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and computer engineering
Computer engineering
Computer engineering, also called computer systems engineering, is a discipline that integrates several fields of electrical engineering and computer science required to develop computer systems. Computer engineers usually have training in electronic engineering, software design, and...
students.
The LC-3 was developed by Yale N. Patt
Yale Patt
Yale Nance Patt is an American professor of electrical and computer engineering at The University of Texas at Austin. He holds the Ernest Cockrell, Jr. Centennial Chair in Engineering. In 1965, Patt introduced the WOS module, the first complex logic gate implemented on a single piece of silicon...
at the University of Texas at Austin
University of Texas at Austin
The University of Texas at Austin is a state research university located in Austin, Texas, USA, and is the flagship institution of the The University of Texas System. Founded in 1883, its campus is located approximately from the Texas State Capitol in Austin...
and Sanjay J. Patel at the University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
. Their specification of the instruction set, the overall architecture of the LC-3, and a hardware implementation can be found in the second edition of their textbook. Courses based on the LC-3 and Patt and Patel's book are offered in many computer engineering and computer science departments.
Architectural specification
The LC-3 specifies a word size of 16 bits for its registers and uses a 16-bit addressable memory with a 216-location address space. The register file contains eight registers, referred to by number as R0 through R7. All of the registers are general-purpose in that they may be freely used by any of the instructions that can write to the register file, but in some contexts (such as translating from C code to LC-3 assembly) some of the registers are used for special purposes.Instructions are 16 bits wide and have 4-bit opcode
Opcode
In computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...
s. The instruction set defines instructions for fifteen of the sixteen possible opcodes, though some instructions have more than one mode of operation. Individual instructions' execution is regulated by a state machine
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
implemented with a control ROM
Read-only memory
Read-only memory is a class of storage medium used in computers and other electronic devices. Data stored in ROM cannot be modified, or can be modified only slowly or with difficulty, so it is mainly used to distribute firmware .In its strictest sense, ROM refers only...
and microsequencing unit.
The architecture supports the use of a keyboard and monitor to regulate input and output; this support is provided through memory mapped I/O abstractions. In simulation, these registers can be accessed directly, and the architectural specification describes their contents. Higher-level I/O support is also provided through the use of the TRAP instruction and a basic operating system. The operating system provides functions to read and echo characters from the keyboard, print individual characters to the monitor, print entire strings in both packed and unpacked forms, and halt the machine.
All data in the LC-3 is assumed to be stored in a two's complement
Two's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
representation; there is no separate support for unsigned arithmetic. The I/O devices operate on ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
characters. The LC-3 has no native support for floating-point numbers.
The hardware implementation given in the Patt and Patel text is not pipelined or otherwise optimized, but it is certainly possible to create a fast implementation using more advanced concepts in computer architecture.
Instruction set
The LC-3 instruction set implements fifteen types of instructions, with a sixteenth opcode reserved for later use. The architecture is a load-store architecture; values in memory must be brought into the register file before they can be operated upon.Arithmetic instructions available include addition, bitwise AND, and bitwise NOT, with the first two of these able to use both registers and sign-extended immediate values as operands. These operations are sufficient to implement a number of basic arithmetic operations, including subtraction (by negating values) and bitwise left shift (by using the addition instruction to multiply values by two). The LC-3 can also implement any bitwise logical function, because NOT and AND together are logically complete.
Memory accesses can be performed by computing addresses based on the current value of the program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
(PC) or a register in the register file; additionally, the LC-3 provides indirect loads and stores, which use a piece of data in memory as an address to load data from or store data to. Values in memory must be brought into the register file before they can be used as part of an arithmetic or logical operation.
The LC-3 provides both conditional and unconditional control flow instructions. Conditional branches are based on the arithmetic sign (negative, zero, or positive) of the last piece of data written into the register file. Unconditional branches may move execution to a location given by a register value or a PC-relative offset. Three instructions (JSR, JSRR, and TRAP) support the notion of subroutine calls by storing the address of the code calling the subroutine into a register before changing the value of the program counter. The LC-3 does not support the direct arithmetic comparison of two values; comparing two register values arithmetically requires subtracting one from the other and evaluating the result.
Programming language support
While it has not been implemented on a physical chip, the LC-3 can be used in simulation on Linux/Unix, Mac OS X and Windows environments. The simulation tools include an assembler with support for computerized offset computation with labels and the insertion of constants, strings, and blank memory locations into a block of assembly code. There is also a convention for using the C language on the LC-3. A sample assembler, compiler, and simulator are provided by McGraw-Hill.C and the LC-3
The calling convention for C functions on the LC-3 is similar to that implemented by other systems, such as the x86 ISA. When running C programs, the architecture maintains a memory model that includes space for a call stackCall stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
and dynamic memory allocation. In this model, four of the processor's eight general purpose registers take on special roles: R4 is used as a base register for loading and storing global data, R5 is used to point to the current function's area on the call stack, and R6 is used as a stack pointer. Additionally, R7 is usually reserved for storage of return addresses from function calls; the JSR, JSRR, and TRAP instructions automatically store return addresses in this register during their execution.
When a C function is called under this model, the function's parameters are pushed onto the stack right to left. Space is then made on the stack for the return value of the function being called, the address of the instruction in the caller to return to, and the caller's value of R5. Local variables in the function being called are pushed onto the stack in the order that they are declared. Note that the LC-3 does not have native PUSH and POP instructions, so addition and memory storage instructions must be used separately to implement the stack.
The LC-3b
The LC-3b ISA describes a modified version of the LC-3 that includes the following changes:- The machine's word size remains 16 bits, but its memory is now byte-addressable with the same address space.
- The LD and ST instructions (load and store data using PC-relative addressing) have been removed.
- The LDI and STI instructions (indirect loads and stores) use register-based addressing instead of PC-relative addressing.
- Two instructions, LDB and STB, have been added to manipulate individual bytes of memory; the other load and store instructions continue to act on entire words.
- The reserved opcode has been converted into a shift instruction, SHF, that supports arithmeticArithmetic shiftIn computer programming, an arithmetic shift is a shift operator, sometimes known as a signed shift . For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are...
and logical shiftLogical shiftIn computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa; every bit in the operand is simply moved a given number of bit...
s of arbitrary size in both directions.
These changes make the hardware of the LC-3b slightly more complex than that of the LC-3. For example, the LC-3b needs a shifter (the LC-3 does not) and extra logic in its memory unit to properly handle loading and storing data of various sizes.
Ashley Wise maintains a set of tools for simulating and working with the LC-3b.
See also
- Educational programming languageEducational programming languageAn educational programming language is a programming language that is designed primarily as a learning instrument and not so much as a tool for writing programs for real-world work.-Learning paths:...
- DLXDLXThe DLX is a RISC processor architecture designed by John L. Hennessy and David A. Patterson, the principal designers of the MIPS and the Berkeley RISC designs , the two benchmark examples of RISC design. The DLX is essentially a cleaned up and simplified MIPS, with a simple 32-bit load/store...
- Little man computerLittle man computerThe Little Man Computer is an instructional model of a computer, created by Dr. Stuart Madnick in 1965. The LMC is generally used to teach students, because it models a simple von Neumann architecture computer - which has all of the basic features of a modern computer...
- MIXMIXMIX is a hypothetical computer used in Donald Knuth's monograph, The Art of Computer Programming . MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machines deemed significant by the author...
, MMIXMMIXMMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites... - MikroSimMikroSimThe program MikroSim is an educational software for hardware-non-specific explanation of the general functioning and behaviour of a virtual processor, running on the operating system Microsoft Windows...