5 ms·

Or try my Hive soft processor core: http://opencores.org/project,hive http://opencores.org/project,hive I need to update the paper and code, the core is at v9

by dewster 10y ago

Or try my Hive soft processor core: http://opencores.org/project,hive http://opencores.org/project,hive I need to update the paper and code, the core is at v9.03 and the simulator can now parse assembly code as input. IMO canonical stack processors aren't a good substitute for register-based processors. Hive is a stack / register hybrid that makes the 2 operand architecture more efficient. And I don't know why barrel processors aren't taking over the world - they make too much sense I suppose.

david-given 10y ago
About a year ago we had this thread: https://news.ycombinator.com/item?id=9920760 https://news.ycombinator.com/item?id=9920760 It's a thesis describing a C compiler for stack machines. (The link in the article is dead now. See https://www-users.cs.york.ac.uk/chrisb/main-pages/publications/ShannonThesis2006.pdf.1 https://www-users.cs.york.ac.uk/chrisb/main-pages/publicatio...) It achieves comparable code density with gcc's x86 (albeit for a fictional architecture). The really interesting bit is Appendix E, which proposes an architecture for a fast stack machine. It uses a fairly traditional 16-bit instruction encoding, except instead of registers each 4-bit operand slot contains an encoded stack manipulation --- a rot or a pick. This should give even better code density while still being easy to implement. Unfortunately I've never tracked down a copy of his compiler...
- throwaway000002 10y ago
  Thanks david for providing that reference. I missed the discussion the first time. Perhaps you, or someone here, would know: has anyone asked and tried to analytically answer what primitive operations an ALU ought to have? I mean, everything could be coded as a look-up-table, but given code "on average", what should be available in hardware. It's a strange question that requires you pose it properly to even begin to answer it. For example, in the kind of stuff I do, popcnt and other "set-like" bit operations, i.e. most-significant set bit, are important enough that I just wish they were built in. Mine you, I'm doing high-performance data processing, so perhaps it's not part of the scope of "average" code, but I disagree.
  - dewster 10y ago
    "...has anyone asked and tried to analytically answer what primitive operations an ALU ought to have?" Very good question. I think this is where the "art" of computer design starts, and it generally gets short shrift. For instance, the ARM lacks a leading zero count instruction, which is a pretty wild omission because it has tons of uses (particularly for floating point) and is fairly expensive to implement in software using other primitives. I know it's not scientific, but I learned what to put in the Hive ALU by programming various algorithms I figured I would need at some point. I just developed a bunch of floating point subroutines for Hive (cos, sin, sqrt, 2^x, log2, 1/x, etc., not in the paper yet) and, short of adding a floating point pipeline, could only really justify adding an opcode that returns +1 / -1 based on the sign bit (for use in storing sign and doing absolute value). My seat of the pants rule is that if it has broad applicability, saves time and code space, and isn't too costly in terms of hardware / speed, then I put it in. Otherwise I leave it out. IMO, more of computer engineering should focus on what to leave out.
    - stephencanon 10y ago
      > For instance, the ARM lacks a leading zero count instruction Huh? ARM has this instruction (since v5, IIRC), it's spelled CLZ.
      - dewster 10y ago
        I've read that ARM Cortex-M0 and M0+ cores do not support it. Why on earth isn't it in all ARM cores?
        stephencanon 10y ago
        M0 is an extraordinarily stripped-down core. While I agree that it would be nice to have CLZ, if you are really missing it on an M0, you'd probably be better off with M3 or M4f.
    - throwaway000002 10y ago
      I had a glance at your Hive paper. Seems like very interesting work. I don't have all the know-how, but if I had the resources, I'd like to build a system where I push compute to a node that essentially is a M.2 SSD glued to a custom core glued to 10G networking. Wire it all up in a Clos network. Use IPv6 and treat it as the address space, throw in a few routing tricks, and call the whole thing a computer. One day I'll build it. Hopefully I can get to that scale at some point.
- dewster 10y ago
  Thanks for the link to that thesis! Appendix E describes I believe what Hive does: a separate bit associated with the operand selector is used to control pop behavior. I'll have to credit this paper in mine (nothing ever really new under the sun). For the rest of the paper, if you look at his "optimized" code there are still a ton of stack ops going on, which are time wasters IMO. This is why three operand machines "won" the techno shootout, a very useful move is included with every instruction. In contrast, well written Hive assembly contains very few time wasting copy / move / pop instructions (for a two operand machine).

by dewster 10y ago

david-given 10y ago

About a year ago we had this thread: https://news.ycombinator.com/item?id=9920760 https://news.ycombinator.com/item?id=9920760 It's a thesis describing a C compiler for stack machines. (The link in the article is dead now. See https://www-users.cs.york.ac.uk/chrisb/main-pages/publications/ShannonThesis2006.pdf.1 https://www-users.cs.york.ac.uk/chrisb/main-pages/publicatio...) It achieves comparable code density with gcc's x86 (albeit for a fictional architecture). The really interesting bit is Appendix E, which proposes an architecture for a fast stack machine. It uses a fairly traditional 16-bit instruction encoding, except instead of registers each 4-bit operand slot contains an encoded stack manipulation --- a rot or a pick. This should give even better code density while still being easy to implement. Unfortunately I've never tracked down a copy of his compiler...

throwaway000002 10y ago
Thanks david for providing that reference. I missed the discussion the first time. Perhaps you, or someone here, would know: has anyone asked and tried to analytically answer what primitive operations an ALU ought to have? I mean, everything could be coded as a look-up-table, but given code "on average", what should be available in hardware. It's a strange question that requires you pose it properly to even begin to answer it. For example, in the kind of stuff I do, popcnt and other "set-like" bit operations, i.e. most-significant set bit, are important enough that I just wish they were built in. Mine you, I'm doing high-performance data processing, so perhaps it's not part of the scope of "average" code, but I disagree.
- dewster 10y ago
  "...has anyone asked and tried to analytically answer what primitive operations an ALU ought to have?" Very good question. I think this is where the "art" of computer design starts, and it generally gets short shrift. For instance, the ARM lacks a leading zero count instruction, which is a pretty wild omission because it has tons of uses (particularly for floating point) and is fairly expensive to implement in software using other primitives. I know it's not scientific, but I learned what to put in the Hive ALU by programming various algorithms I figured I would need at some point. I just developed a bunch of floating point subroutines for Hive (cos, sin, sqrt, 2^x, log2, 1/x, etc., not in the paper yet) and, short of adding a floating point pipeline, could only really justify adding an opcode that returns +1 / -1 based on the sign bit (for use in storing sign and doing absolute value). My seat of the pants rule is that if it has broad applicability, saves time and code space, and isn't too costly in terms of hardware / speed, then I put it in. Otherwise I leave it out. IMO, more of computer engineering should focus on what to leave out.
  - stephencanon 10y ago
    > For instance, the ARM lacks a leading zero count instruction Huh? ARM has this instruction (since v5, IIRC), it's spelled CLZ.
    - dewster 10y ago
      I've read that ARM Cortex-M0 and M0+ cores do not support it. Why on earth isn't it in all ARM cores?
      - stephencanon 10y ago
        M0 is an extraordinarily stripped-down core. While I agree that it would be nice to have CLZ, if you are really missing it on an M0, you'd probably be better off with M3 or M4f.
  - throwaway000002 10y ago
    I had a glance at your Hive paper. Seems like very interesting work. I don't have all the know-how, but if I had the resources, I'd like to build a system where I push compute to a node that essentially is a M.2 SSD glued to a custom core glued to 10G networking. Wire it all up in a Clos network. Use IPv6 and treat it as the address space, throw in a few routing tricks, and call the whole thing a computer. One day I'll build it. Hopefully I can get to that scale at some point.
dewster 10y ago
Thanks for the link to that thesis! Appendix E describes I believe what Hive does: a separate bit associated with the operand selector is used to control pop behavior. I'll have to credit this paper in mine (nothing ever really new under the sun). For the rest of the paper, if you look at his "optimized" code there are still a ton of stack ops going on, which are time wasters IMO. This is why three operand machines "won" the techno shootout, a very useful move is included with every instruction. In contrast, well written Hive assembly contains very few time wasting copy / move / pop instructions (for a two operand machine).