Misplaced Pages

#580419

43-397: For example, data might be stored notionally in a single sequence like a row, in two dimensions like rows and columns on a surface, or in multiple dimensions. However, given all the coordinates, a program can access each record about as quickly and easily as any other. In this sense, the choice of datum is arbitrary in the sense that no matter which item is sought, all that is needed to find it

86-477: A collection, but the maximum time to retrieve a given member grows only logarithmically with its size. Drum memory Drum memory was a magnetic data storage device invented by Gustav Tauschek in 1932 in Austria . Drums were widely used in the 1950s and into the 1960s as computer memory . Many early computers, called drum computers or drum machines, used drum memory as the main working memory of

129-564: A delay line was 1024 microseconds. Instruction times were: addition, subtraction, logical operations: 64 microseconds for 32-bit words; double-precision 96 microseconds; multiplication and division 2 milliseconds. For array arithmetic and transfer operations, time per word was 33 microseconds per word for 32 words. Floating-point operations were provided by software; times: 6 milliseconds for addition and subtraction, 5.5 milliseconds average for multiplication, and 4.5 milliseconds average for division. In

172-578: A paper disclosing "air floating" of magnetic heads in an experimental sheet metal drum. A US patent filed in January 1954 by Baumeister of IBM disclosed a "spring loaded and air supported shoe for poising a magnetic head above a rapidly rotating magnetic drum." Flying heads became standard in drums and hard disk drives . Magnetic drum units used as primary memory were addressed by word. Drum units used as secondary storage were addressed by block. Several modes of block addressing were possible, depending on

215-492: A value, n, and then reads in n binary integers. It punches out the integer and its square. Comments in lower case explain the instruction. STAC would produce the following instructions (in addition to the binary program). The memory location of each instruction is shown at the left. Wait and timing numbers are not shown, except for the multiplication. Programming the DEUCE was different from other computers. The serial nature of

258-436: A word at a time, a pair of words at a time, and any number of words up to 33 at a time. Thus, for example, 32 words read from the drum could be transferred as a block to any of the other delay lines; 4 words could be transferred as a block from one quadruple register to the other, or between a quadruple register and a delay line—all with one instruction. The 32 words of a delay line could be summed by passing them to

301-523: Is a cassette tape (sequential — one must fast forward through earlier songs to get to later ones) and a CD (direct access — one can skip to the track wanted, knowing that it would be the one retrieved). In data structures , direct access implies the ability to access any entry in a list in constant time (independent of its position in the list and of the list's size). Very few data structures can make this guarantee other than arrays (and related structures like dynamic arrays ). Direct access

344-462: Is its address, i.e. the coordinates at which it is located, such as its row and column (or its track and record number on a magnetic drum ). At first, the term "random access" was used because the process had to be capable of finding records no matter in which sequence they were required. However, soon the term "direct access" gained favour because one could directly retrieve a record, no matter what its position might be. The operative attribute, however,

387-405: Is required, or at least valuable, in many algorithms such as binary search , integer sorting , or certain versions of sieve of Eratosthenes . Other data structures, such as linked lists , sacrifice direct access to permit efficient inserts, deletes, or re-ordering of data. Self-balancing binary search trees may provide an acceptable compromise, where access time is not equal for all members of

430-413: Is that the device can access any required record immediately on demand. The opposite is sequential access , where a remote element takes longer time to access. A typical illustration of this distinction is to compare an ancient scroll (sequential; all material prior to the data needed must be unrolled) and the book (direct: can be immediately flipped open to any arbitrary page ). A more modern example

473-442: The 1970s. A drum memory or drum storage unit contained a large metal cylinder, coated on the outside surface with a ferromagnetic recording material. It could be considered the precursor to the hard disk drive (HDD), but in the form of a drum (cylinder) rather than a flat disk. In most designs, one or more rows of fixed read-write heads ran along the long axis of the drum, one for each track. The drum's controller simply selected

SECTION 10

#1732800899581

516-524: The Hollerith equipment, giving the same input/output speeds, in which case the machine was called Mark II. Automatic conversion of alphanumeric data to BCD was provided on input, and the reverse operation on output, for all eighty card columns. On this equipment, reading and punching could proceed simultaneously, if required, and thus could be used for reading in a record, updating it, and then punching an updated record simultaneously with reading in

559-690: The Navy on June 19, 1947. Other early drum storage device development occurred at Birkbeck College ( University of London ), Harvard University , IBM and the University of Manchester . An ERA drum was the internal memory for the ATLAS-I computer delivered to the U.S. Navy in October 1950 and later sold commercially as the ERA 1101 and UNIVAC 1101 . Through mergers , ERA became a division of UNIVAC shipping

602-626: The Series 1100 drum as a part of the UNIVAC File Computer in 1956; each drum stored 180,000 6-bit characters (135 kilobytes). The first mass-produced computer, the IBM 650 (1954), initially had up to 2,000 10-digit words, about 17.5 kilobytes , of drum memory (later doubled to 4,000 words, about 35 kilobytes, in the Model 4). In BSD Unix and its descendants, /dev/drum was the name of

645-426: The card punch; the word for a particular row was prepared in advance and had to be ready when a given row of the card was in position under the punch knives. The normal mode of reading and punching was binary. Decimal input and output was performed via software. The high-speed store consisted of four single-word registers of 32 bits each, three double-word registers, and two quadruple-word registers. Each 32-bit word of

688-410: The codewords. Dimensions were taken from the matrices themselves, either from a card preceding the data cards or from the matrices as stored on drum. Thus, programs were entirely general. Once written, such a program handled any size of matrices (up to the capacity of the drum, of course). A short program to read in a matrix from cards, to transpose the matrix, and to punch the results on cards requires

731-443: The computer to be ready to read the next one, then placing that instruction on the drum so that it would arrive under a head just in time. This method of timing-compensation, called the "skip factor" or " interleaving ", was used for many years in storage memory controllers. Tauschek's original drum memory (1932) had a capacity of about 500,000 bits (62.5 kilobytes ). One of the earliest functioning computers to employ drum memory

774-572: The computer. Some drums were also used as secondary storage as for example various IBM drum storage drives and the UNIVAC FASTRAND series of drums. Drums were displaced as primary computer memory by magnetic core memory , which offered a better balance of size, speed, cost, reliability and potential for further improvements. Drums were then replaced by hard disk drives for secondary storage , which were both less expensive and offered denser storage. The manufacturing of drums ceased in

817-544: The default virtual memory (swap) device, deriving from the historical use of drum secondary-storage devices as backup storage for pages in virtual memory . Magnetic drum memory units were used in the Minuteman ICBM launch control centers from the beginning in the early 1960s until the REACT upgrades in the mid-1990s. English Electric DEUCE The DEUCE ( Digital Electronic Universal Computing Engine )

860-465: The delay lines required that instructions be ordered such that when one instruction completed execution, the next one was ready to emerge from a Delay Line. For operations on the single registers, the earliest time that the next instruction could be obeyed was 64 microseconds after the present one. Thus, instructions were not executed from sequential locations. In general, instructions could transfer one or more words. Consequently, each instruction specified

903-411: The device. Some devices were divided into logical cylinders, and addressing by track was actually logical cylinder and track. The performance of a drum with one head per track is comparable to that of a disk with one head per track and is determined almost entirely by the rotational latency, whereas in an HDD with moving heads its performance includes a rotational latency delay plus the time to position

SECTION 20

#1732800899581

946-444: The double and quadruple-word registers could be addressed separately. They could also be accessed as a pair, and—in the case of the quadruple registers—as a group of three or four. The instruction store consisted of twelve mercury delay lines , each of 32 words, and numbered 1 to 12. Delay line 11 (DL11) served as the buffer between the magnetic drum and the high-speed store. Being a "transfer machine", data could be transferred

989-429: The early machines, all instructions involving the magnetic drum were interlocked while an operation was in progress. Thus, if the read heads were moved, any subsequent magnetics operation such as to read a track or write a track, were prohibited from proceeding until the first had completed. From about 1957, a new unit, called "rationalised magnetics" was made available. This unit eliminated unnecessary interlocks. Thus, it

1032-523: The engine manufacturer Bristol Siddeley . The success of DEUCE was due to its program library of over 1000 programs and subroutines. DEUCE Mark 0 and I: DEUCE MARK II: DEUCE MARK IA AND IIA: Notes: The multiplier and divider were asynchronous. Several integers could be multiplied in a single execution of the multiply instruction, by inserting integers in the multiplier or multiplicand registers during multiplication, and by extracting results during multiplication. Other special effects included counting

1075-419: The following codewords: In each of the codewords, the fourth number is the brick number. The first codeword specifies that the matrix is read from cards and stored at drum address 5; the second codeword specifies that the matrix at drum address 5 is transposed, and the result is stored at drum address 120; and the third punches that result on cards. STAC was a macro-assembler. Most instructions were written in

1118-450: The form of a transfer, in decimal, such as 13-16, meaning to copy the word in register 13 to register 16. The location of the instruction was not specified. STAC allocated an instruction to a word in a delay line, and computed the six components of the binary instruction. It allocated the next instruction to a location that was optimum, to be executed as soon as the previous instruction was complete, if possible. The following program reads in

1161-450: The head over the desired track ( seek time ). In the era when drums were used as main working memory, programmers often did optimum programming —the programmer—or the assembler, e.g., Symbolic Optimal Assembly Program (SOAP)—positioned code on the drum in such a way as to reduce the amount of time needed for the next instruction to rotate into place under the head. They did this by timing how long it would take after loading an instruction for

1204-428: The location of the next instruction. Optimum programming meant that as each instruction was executed, the next one was just emerging from a Delay Line. The position of instructions in the store could greatly affect performance if the location of an instruction was not optimum. Reading data from the card reader was done in real-time – each row had to be read as it passed the read brushes, without stopping. Similarly for

1247-516: The next record. With the seven extra delay lines, the DEUCE was denoted Mark IIA. The principal high-level programming languages were GEORGE (General Order Generator), ALPHACODE, STEVE, TIP, GIP, and ALGOL . Assembler language translators included ZP43 and STAC. Invented by Charles Leonard Hamblin in 1957, GEORGE was closest to present-day programming languages. It used Reverse Polish Notation . For example, to evaluate e = ay + by + c , one wrote where "dup" duplicates

1290-405: The paper tape output speed was 25 characters per second. (The DEUCE at the University of New South Wales {UTECOM} had a Siemens M100 teleprinter attached in 1964, giving 10 characters per second input/output). Decca magnetic tape units could also be attached. The automatic multiplier and divider operated asynchronously (that is, other instructions could be executed while the multiplier/divider unit

1333-423: The previous entry, being the same as using "y" here. GEORGE provided a 12-position accumulator as a push-down pop-up stack. Using a variable name in a program (e.g., 'd') brought the value of variable 'd' into the accumulator (i.e., pushed d onto the top-of-stack), while enclosing a name in parentheses {e.g., (d) } assigned to variable 'd' the value at the top of the stack (accumulator). To destroy (pop and discard)

Random access - Misplaced Pages Continue

1376-543: The proper head and waited for the data to appear under it as the drum turned ( rotational latency ). Not all drum units were designed with each track having its own head. Some, such as the English Electric DEUCE drum and the UNIVAC FASTRAND had multiple heads moving a short distance on the drum in contrast to modern HDDs, which have one head per platter surface. In November 1953 Hagen published

1419-444: The quadruple registers were associated with an auto-increment/decrement facility. That facility could be used for counting and for modifying instructions (for indexing, loop control, and for changing the source or destination address of an instruction). Being a bit-serial machine, access time to a single register was 32 microseconds, a double register 64 microseconds, and a quadruple register 128 microseconds. That for

1462-448: The separate Hollerith units on the earlier DEUCE Mark I machines; however, it was also provided with hardware conversion of alphanumeric data to BCD on input, and vice versa on output. Data could also be read in and punched simultaneously at 100 cards per minute. The DEUCE Mark IIA provided seven extra mercury delay lines, each of 32 words. A total of 33 DEUCE machines were sold between 1955 and 1964, two being purchased by

1505-419: The single-length adder (by means of a single instruction). By a special link between DL10 and one register, namely, register 16, DL10 could be used as a push-down stack. The first three machines were delivered in the spring of 1955; in late 1958 a DEUCE Mark II improved model appeared. This version employed a combined card reader and punch. The combined IBM 528 reader and punch behaved like

1548-568: The then high 1  megahertz clock rate of the Pilot ACE. Input/output was via Hollerith 80-column punch-card equipment. The reader read cards at the rate of 200 per minute, while the card punch rate was 100 cards per minute. The DEUCE also had an 8192-word magnetic drum for main storage. To access any of the 256 tracks of 32 words, the drum had one group of 16 read and one group of 16 write heads, each group on independent moveable arms, each capable of moving to one of 16 positions. Access time

1591-414: The value at the top of the stack, the semicolon (;) was used. The following GEORGE program reads in ten numbers and prints their squares: In the above program, the "dup" command duplicated the top of the stack, so that there were then two copies of the value at the top of the stack. GIP (General Interpretive Programme) was a control program for manipulating programs called "bricks". Its principal service

1634-400: Was 15 milliseconds if the heads were already in position; an additional 35 milliseconds was required if the heads had to be moved. There was no rotational delay incurred when reading from and writing to drum. Data was transferred between the drum and one of the 32-word delay lines. The DEUCE could be fitted with paper tape equipment; the reader speed was 850 characters per second, while

1677-501: Was in operation). Two arithmetic units were provided for integer operations: one of 32 bits and another capable of performing 32-bit operations and 64-bit operations. Auto-increment and auto-decrement were provided on eight registers from about 1957. Array arithmetic and array data transfers were permitted. Compared with contemporaries such as the Manchester Mark 1 , DEUCE was about ten times faster. The individual words of

1720-589: Was in the running of programs from the several hundred in the DEUCE linear algebra library. Preparation of such a program involved selecting the required bricks (on punch cards), copying them and GIP in a reproducing punch, and assembling the copies into a deck of cards. Next, simple codewords would be written to use the bricks to perform such tasks as: matrix multiplication; matrix inversion; term-by-term matrix arithmetic (addition, subtraction, multiplication, and division); solving simultaneous equations; input; and output. The dimensions of matrices were never specified in

1763-463: Was one of the earliest British commercially available computers , built by English Electric from 1955. It was the production version of the Pilot ACE , itself a cut-down version of Alan Turing 's ACE . The DEUCE had 1450 thermionic valves , and used mercury delay lines for its main memory ; each of the 12 delay lines could store 32 instructions or data words of 32 bits each. It adopted

Random access - Misplaced Pages Continue

1806-594: Was possible to execute an instruction that moved the read heads: if followed by an instruction to move the write heads, or to write a track, such instructions were not interlocked, and could proceed in parallel with moving the read heads. The front panel of the DEUCE featured two CRT displays : one showed the current contents of registers, while the other showed the content of any one of the mercury delay line stores. From about 1958, seven extra delay lines could be attached, giving 224 more words of high-speed store. An IBM 528 combined reader–punch could be substituted for

1849-485: Was the Atanasoff–Berry computer (1942). It stored 3,000 bits; however, it employed capacitance rather than magnetism to store the information. The outer surface of the drum was lined with electrical contacts leading to capacitors contained within. Magnetic drums were developed for the U.S. Navy by Engineering Research Associates (ERA) in 1946 and 1947. An experimental ERA study was completed and reported to

#580419