Re: [math-fun] History of swap/exch computer instructions ?
On 2018-03-13 17:21, Henry Baker wrote:
Thanks, Rich!
I looked at the 7094 instruction set manual online, but didn't see anything like an exchange/swap instruction.
I looked at an online GE645 instruction set manual, but didn't find anything there.
Exchange/swap were considered back then for two reasons:
1. memory & registers were extremely expensive, so a single instruction exchange/swap would save both data/register memory and instruction memory.
2. main memory was made from ferrite cores, so reading was *destructive*. Since you had to write *something* back to memory anyway, you might as well write something *else* just as easily as writing back what you just read.
(The PDP-8 curiously did this backwards: its "DCA" (Deposit and Clear Accumulator) stored the accumulator and set it to zero, but the "LDA" (LoaD Accumulator) instruction did *not* clear the memory location from which it was loaded! It would be interesting to know if there were any computers who "utilized" this *destructive read* "feature" of core memory.)
I do recall that some computers back then had the ability to exchange a memory location with the *program counter*! This enabled fast Fortran I subroutining (no stack; no recursion; no service) and "co-routining". Perhaps the PDP-6/10 did this sort of thing as well.
Yes, JSP A,(A) . The PDP-6 had every imaginable subroutine instruction, jsp, jsr, jda, and, of course pushj, the latter as a sop to the Lisp community. Ironically, pushj turned out to be so fantastically useful that hardly anybody used the others. There was also UUO (unused opcode), which trapped to a uuo handler that could implement any kind of calling sequence you could dream up. It was sometimes possible to "outbum" pushj code using using jsp with an "implicit calling sequence". Instead of storing arguments after the jsp and then skipping over them upon return, you returned to the immediately subsequent instructions, which contrived to mention the arguments, which the subroutine fetched via (possibly multilevel) indirect addressing, with indexing at every level. Given the 16 triple purpose accumulators, it was usually possible to rearrange your steps to suit the expectations of the subroutine. And, of course, you could transmit multiple arguments in the accumulators. It was the greatest order code ever devised. --rwg Also, I think HAKMEM mentions representing free storage as a linked list of exch instructions. (Talk about data execution.) At the time, the machine was ridiculed for devoting an entire halfword (18 bits) to address memory, since nobody could need nor afford an entire megabyte. Instead of "Just you wait!", DEC mumbled meekly about symmetry.
At 03:59 PM 3/13/2018, rcs@xmission.com wrote:
The PDP6 had EXCH A,M which swapped an Accumulator with a Memory location. The manual is dated 1964.
At that time, EXCH as an atomic instruction was believed useful for
certain
safely-interruptible algorithms --- futzing with linked lists &c.
Maybe check out an old IBM 7094 manual?
Rich ---- Quoting Michael Greenwald <mbgreen@seas.upenn.edu>:
On 2018-03-08 08:10, Henry Baker wrote:
I'm curious as to the origin of the exch/swap instruction in computer instruction sets.
Does anyone know the first computer having such an instruction?
I'm not interested in the modern "compare-and-swap" type of instruction, which seems to have originated with Maurice Herlihy, but the original, non-conditional type.
I don't think Maurice originated the instruction; I am pretty sure some versions of it predated him by decades (IBM 370). He was just the one who pointed out and proved that it was universal (in the context of non-blocking synchronization), as was the pair LL SC.
But I have no answer to your main question, sorry.
Yes, early computer scientists (before they were called that!) loved these instructions because they allowed for clever algorithms like a stackless GC algorithm.
The TX-2 (circa 1960) had an exchange instruction, EXA. See http://bitsavers.org/pdf/mit/tx-2/TX-2_UsersHandbook_Nov63.pdf . --prs. On Mar 13, 2018, at 11:15 PM, Bill Gosper <billgosper@gmail.com> wrote:
On 2018-03-13 17:21, Henry Baker wrote:
Thanks, Rich!
I looked at the 7094 instruction set manual online, but didn't see anything like an exchange/swap instruction.
I looked at an online GE645 instruction set manual, but didn't find anything there.
Exchange/swap were considered back then for two reasons:
1. memory & registers were extremely expensive, so a single instruction exchange/swap would save both data/register memory and instruction memory.
2. main memory was made from ferrite cores, so reading was *destructive*. Since you had to write *something* back to memory anyway, you might as well write something *else* just as easily as writing back what you just read.
(The PDP-8 curiously did this backwards: its "DCA" (Deposit and Clear Accumulator) stored the accumulator and set it to zero, but the "LDA" (LoaD Accumulator) instruction did *not* clear the memory location from which it was loaded! It would be interesting to know if there were any computers who "utilized" this *destructive read* "feature" of core memory.)
I do recall that some computers back then had the ability to exchange a memory location with the *program counter*! This enabled fast Fortran I subroutining (no stack; no recursion; no service) and "co-routining". Perhaps the PDP-6/10 did this sort of thing as well.
Yes, JSP A,(A) . The PDP-6 had every imaginable subroutine instruction, jsp, jsr, jda, and, of course pushj, the latter as a sop to the Lisp community. Ironically, pushj turned out to be so fantastically useful that hardly anybody used the others. There was also UUO (unused opcode), which trapped to a uuo handler that could implement any kind of calling sequence you could dream up. It was sometimes possible to "outbum" pushj code using using jsp with an "implicit calling sequence". Instead of storing arguments after the jsp and then skipping over them upon return, you returned to the immediately subsequent instructions, which contrived to mention the arguments, which the subroutine fetched via (possibly multilevel) indirect addressing, with indexing at every level. Given the 16 triple purpose accumulators, it was usually possible to rearrange your steps to suit the expectations of the subroutine. And, of course, you could transmit multiple arguments in the accumulators. It was the greatest order code ever devised. --rwg Also, I think HAKMEM mentions representing free storage as a linked list of exch instructions. (Talk about data execution.)
At the time, the machine was ridiculed for devoting an entire halfword (18 bits) to address memory, since nobody could need nor afford an entire megabyte. Instead of "Just you wait!", DEC mumbled meekly about symmetry.
At 03:59 PM 3/13/2018, rcs@xmission.com wrote:
The PDP6 had EXCH A,M which swapped an Accumulator with a Memory location. The manual is dated 1964.
At that time, EXCH as an atomic instruction was believed useful for certain safely-interruptible algorithms --- futzing with linked lists &c.
Maybe check out an old IBM 7094 manual?
Rich ---- Quoting Michael Greenwald <mbgreen@seas.upenn.edu>:
On 2018-03-08 08:10, Henry Baker wrote:
I'm curious as to the origin of the exch/swap instruction in computer instruction sets.
Does anyone know the first computer having such an instruction?
I'm not interested in the modern "compare-and-swap" type of instruction, which seems to have originated with Maurice Herlihy, but the original, non-conditional type.
I don't think Maurice originated the instruction; I am pretty sure some versions of it predated him by decades (IBM 370). He was just the one who pointed out and proved that it was universal (in the context of non-blocking synchronization), as was the pair LL SC.
But I have no answer to your main question, sorry.
Yes, early computer scientists (before they were called that!) loved these instructions because they allowed for clever algorithms like a stackless GC algorithm.
Indeed the TX-2 did! So perhaps the TX-2 is "ground zero" for exch/swap instructions?? "EXCHANGE A is a combination of STA and LDA." EXA (TX-2 manual, page 3-10, 3-11) "The two copy operations that perform an exchange *take place simultaneously.*" Also EXX. "EXX is a combination of RSX and DPX." EXX (TX-2 manual, page 3-18, 3-19) --- I wasn't able to understand all of the various TX-2 subroutine call & return instructions, but one or more may have also done some exchanging/swapping/permuting with the PC. --- The TX-2 manual is dated July 1961, but Wikipedia says "The TX-2 became operational in 1958." --- I didn't do a thorough search, but it doesn't look like the British computers did exchanges/swaps, although at least one had a reverse Polish stack. Don't know about Soviet computers -- e.g., BESM. At 11:14 AM 3/14/2018, prs@gricer.com wrote:
The TX-2 (circa 1960) had an exchange instruction, EXA.
See http://bitsavers.org/pdf/mit/tx-2/TX-2_UsersHandbook_Nov63.pdf .
--prs.
participants (3)
-
Bill Gosper -
Henry Baker -
prs＠gricer.com