8

The HP/1000 was considered like a 16-bit "expansion" of the 12-bit DEC PDP-8.  Its addressing mode for loads and stores similarly used pages, base page and current page, and allowed for indirection.

However, during indirect load or store, the HP/1000 used only 15-bits of the memory word as pointer to address memory, reserving the high bit in the loaded pointer to request an additional indirection: as long as the loaded pointers had their high bit set the HP/1000 would continue indirection for that instruction.

One architectural cost for this feature was 1 bit of address space, so given this feature, the computer could only access 215 words instead of 216 words — effectively halving the potential address space.  This extra capacity and much more was in demand for many applications, and, like the PDP-8, they had to use alternative mechanisms to address larger capacities (they would have had to do this anyway, but an additional 32k of directly addressable words would have been put to good use).

I'm interested in any code sequences that would have motivated architecting or would have benefited from using the multiple/repeating indirection feature.  (I did compiler work for the HP/1000 and never used that feature!)

  • 1
    Can you crash the machine by letting two pointers point to eachother? – Wilson May 3 '18 at 7:36
  • 1
    The PDP-10 apparently had a similar thing or the same thing. It can be done on any computer that had a wider databus than address bus. – Wilson May 3 '18 at 10:12
  • @Wilson, Yes, I believe you can set up infinite indirection, which will hang the program. I think it still takes interrupts, though, unless the indirection is used in a branch instruction (a feature for something about returning from interrupts, iirc). – Erik Eidt May 3 '18 at 14:20
  • @Wilson assuming HP2000 was no different, I saw this myself. Location 0 containing 0 with bit 15 set. If you pressed single step, it would stay in "run" until you pressed halt. So you didn't even need two pointers; just one pointing to itself. – gbarry May 5 '18 at 6:20
  • 2
    The Data General NOVA series had the same feature, and had the same problem, i.e. a self-pointing indirect pointer would hang the machine. – A. I. Breveleri May 7 '18 at 14:26
4

It's a very handy feature for linked lists (*1). One can access the last entry of a linked list in a single machine instruction, as if it was used directly.

Examples:

Lets assume a list of blocks, where data always has to be added to the last one - like in a high throughput logging, where one (or more) tasks add data and another one writes it to disk. Adding data by the loggers needs to be fast, so with this instruction they seamlessly address the block to be used.

Another application would be a stack organized as a linked list. Here also the last block is usually the one to be accessed. The addressing will do so without much management and at maximum speed.

The Siemens X and Z CPUs (/370 compatible) had similar (even more more powerful) linked list instructions added. Using them within BS2000 (their Mainframe-OS) for stack handling did speed up the OS by ~20% over all.

There where microprocessors with the same features - like the Valvo 2650.


*1 - Useless features get rarely implemented - especially not from multiple teams in different machines/processor. This allone should quality as a proof that it'll be useful.

  • 2
    I'm not quite clear on your examples. If you want to find the last element in a sequence, it should be faster to maintain a pointer to it. Traipsing through memory with a single instruction seems powerful, but you're still paying to walk through all those addresses. I'm certainly biased by modern hardware, where the cost of accessing memory is proportionally much higher than the cost of executing an instruction. But even with slower instruction execution, I'm not sure why this would provide a significant performance advantage vs. a smarter data structure. – fadden May 3 '18 at 22:20
  • Lets start with its atomic nature? If you're climbing a list in a multi tasking environmen you would need to lock it before walking,so no other process can change it while you're trying to find the last entry. Second would be the speed. Walking under software control means at least 2 instructions in loop, each tripling the memory load compared to what the indirect access needs (Two instruction loads in addition to the pointer load) - even worse if a test had to be done and maybe even some maskingbefore using. Such an instruction offers a a considerable perforance gain. – Raffzahn May 4 '18 at 9:43
  • Atomicity assumes that instructions cannot be interrupted mid-flight; I don't know if that's the case here. Even if they can't, there are few situations where you wouldn't want explicit locking on data shared read-write between processes. (This also opens a whole can of worms about the memory model.) With regard to the speed of walking the list, my point was more that a different data structure might obviate the need for walking entirely, e.g. maintaining a pointer to head and tail of a list rather than knowing only the head and always walking to the tail. – fadden May 4 '18 at 19:20
  • There are many situations, this likely being one of them, where it is easier to make a feature be usable for a few useful cases and many useless ones, than it would be to limit the feature to cases that were expected to be useful. Unless there would be an advantage to limiting the feature (e.g. leaving a range of opcode space available for future expansion) it's often better to let customers decide what features they find useful than to expend effort blocking cases that could otherwise have helped serve customers' needs. – supercat Nov 26 '18 at 21:20
1

I'm not familiar with the HP/1000, so if you get an answer from someone with specific knowledge, you should accept that one. However:

In thirty-six years of programming, I have never heard of a situation where that feature would be particularly useful.

On the other hand, I have seen a tendency of good engineers to reflexively generalize, i.e. to follow an implicit rule 'allow the general case whenever it won't cost much extra' rather than 'stick to the special case unless there is a need for the general case'. Certainly there is a use for a single level of pointer indirection, and the direct cost of providing N levels would be small.

The indirect cost of sacrificing half the address space was, as you say, large. But according to Wikipedia, that machine was invented in 1966. Did address space look like a significant constraint at that time? Or did it look like 32K should be enough for anyone?

  • 2
    There were systems (e.g., IBM 360) produced around the same time with a lot more memory. However, for a small machine at the time 32K would have quite large. A quick search found a manual from a later version (several years later) that started with only 16K of memory, so it is quite possible that at the time it was introduced HP did not plan on the 1000 ever supporting more than 32K - i.e., if you want more than that move up to a different product line. – manassehkatz May 3 '18 at 14:19
  • 3
    "In thirty-six years of programming, I have never heard of a situation where that feature would be particularly useful.". I hadn't either, and I even wrote code generators for the HP/1000... – Erik Eidt May 3 '18 at 18:51
1

Taking a look at the Wikipedia article, it's pretty clear what the indirection bit was for: to access memory that was not in the current or zero pages (the current page was taken from the program counter register, and you chose which page to access with a page indicator.) It also appears that the HP 1000 didn't have a stack register, so procedure calls used this mechanism as well to store return addresses.

Essentially, the indirect bit was a way to optimize for same-page memory accesses but still allow access to the entire memory space. It's pretty clever, IMO.

  • 1
    I think the question was more about why that bit is in the pointer itself rather than in the instruction – Wilson May 5 '18 at 7:58
  • @Wilson, you are correct that the question was about the extra indirection bit(s) in each word loaded from memory as pointer, and that the indirection would continue as long as the pointer loaded from memory had that bit set (rather than about the indirection bit in the instruction word). In particular, this was a difference between the PDP-8 and the HP/1000 -- the PDP-8 supported only one level of indirection supplied in the (indirect bit of an) instruction and didn't support additional indirection specified in the pointer. – Erik Eidt May 5 '18 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.