5 ms·

Tangential question: how does single cycle multiplication works in arm cortex processors? Do they just run the ALU clock fast enough that the multiplication fin

Tangential question: how does single cycle multiplication works in arm cortex processors? Do they just run the ALU clock fast enough that the multiplication finishes in one visible core cycle or is there a binary trick?

hatsunearu 8y ago
Any binary operation (subject to the usual "well behaved" caveat) can be split up into any number of steps; this is called pipelining. In fact there's not really a reason why multiplication isn't a single cycle step, other than speed and energy efficiency. The maximum clock speed of an operation is limited by how fast a change in the input can be propagated into the correct change in output. You can get around this by splitting the operation into multiple mini-steps (pipelining) and clocking it to as fast as the slowest stage will go.
_0ffh 8y ago
The paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.
- wbhart 8y ago
  Is there a known example of something a digital computer can do that a Turing machine cannot?
  - your-nanny 8y ago
    overheat.
  - Retra 8y ago
    Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
  - pmiller2 8y ago
    In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
    - kps 8y ago
      Real computers generally have external storage and/or network interfaces, which makes them unbounded.
      - pmiller2 8y ago
        No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.
  - wolfgke 8y ago
    > Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".
- ChrisLomont 8y ago
  >Actual digital circuits are not bound to that constraint. Yes they are. Hardware can parallelize, but does not remove asymptotic complexity for arbitrarily sized problems. It only changes the hidden constant cost. The paper result is for unbounded size for n. Hardware has fixed size n, and for a fixed size n, any problem is constant time O(1).
  - systemBuilder 8y ago
    Andy Yao proved a lower bound on circuit complexity for multiplication of circuit width x depth = Omega(n ^ 2). Trivial carry circuits for adders are O(n).
  - _0ffh 8y ago
    Hardware might have fixed size n, but a general approach certainly doesn't! I must have failed badly at making my point clearly, because I've got that same criticism more than once. Take as an example this paper [1], which explicitly states the delay of an n-bit Baugh-Wooley multiplier as O(log n). I appreciate that this might not be what people are discussing here - if so, excuse me mixing things up. I answered to a question that asked about a connection between the Turing machine algorithm and practical circuit design, and I tried as best I could to give a practical circuit design perspective. [1] https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf
    - ChrisLomont 8y ago
      I'm familiar with such results. TAOCP has quite a few I've fiddled with over the years. It has an O(n) multiply, for example. Most (all?) algorithms can be made O(log n) by throwing hardware at it. The hardware is basically a lookup table, and you can inspect each bit of a length n problem in O(log n) time, and output the answer. Papers like this use problem structure to reduce the general exponential circuit growth to (usually) ~linear growth. But all I've seen require unbounded circuit growth, as does this one, which is O(n log n) circuit size. By allowing hardware to grow at unbounded rate, it's not really solving the same problem.
userbinator 8y ago
Multiplication is done in hardware with a large parallel array of product and sum components: https://en.wikipedia.org/wiki/Dadda_multiplier https://en.wikipedia.org/wiki/Dadda_multiplier Pipelining, as mentioned in a sibling comment, is used to increase throughput.

hatsunearu 8y ago

Any binary operation (subject to the usual "well behaved" caveat) can be split up into any number of steps; this is called pipelining. In fact there's not really a reason why multiplication isn't a single cycle step, other than speed and energy efficiency. The maximum clock speed of an operation is limited by how fast a change in the input can be propagated into the correct change in output. You can get around this by splitting the operation into multiple mini-steps (pipelining) and clocking it to as fast as the slowest stage will go.

_0ffh 8y ago

The paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.

wbhart 8y ago
Is there a known example of something a digital computer can do that a Turing machine cannot?
- your-nanny 8y ago
  overheat.
- Retra 8y ago
  Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
- pmiller2 8y ago
  In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
  - kps 8y ago
    Real computers generally have external storage and/or network interfaces, which makes them unbounded.
    - pmiller2 8y ago
      No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.
- wolfgke 8y ago
  > Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".
ChrisLomont 8y ago
>Actual digital circuits are not bound to that constraint. Yes they are. Hardware can parallelize, but does not remove asymptotic complexity for arbitrarily sized problems. It only changes the hidden constant cost. The paper result is for unbounded size for n. Hardware has fixed size n, and for a fixed size n, any problem is constant time O(1).
- systemBuilder 8y ago
  Andy Yao proved a lower bound on circuit complexity for multiplication of circuit width x depth = Omega(n ^ 2). Trivial carry circuits for adders are O(n).
- _0ffh 8y ago
  Hardware might have fixed size n, but a general approach certainly doesn't! I must have failed badly at making my point clearly, because I've got that same criticism more than once. Take as an example this paper [1], which explicitly states the delay of an n-bit Baugh-Wooley multiplier as O(log n). I appreciate that this might not be what people are discussing here - if so, excuse me mixing things up. I answered to a question that asked about a connection between the Turing machine algorithm and practical circuit design, and I tried as best I could to give a practical circuit design perspective. [1] https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf
  - ChrisLomont 8y ago
    I'm familiar with such results. TAOCP has quite a few I've fiddled with over the years. It has an O(n) multiply, for example. Most (all?) algorithms can be made O(log n) by throwing hardware at it. The hardware is basically a lookup table, and you can inspect each bit of a length n problem in O(log n) time, and output the answer. Papers like this use problem structure to reduce the general exponential circuit growth to (usually) ~linear growth. But all I've seen require unbounded circuit growth, as does this one, which is O(n log n) circuit size. By allowing hardware to grow at unbounded rate, it's not really solving the same problem.

userbinator 8y ago

Multiplication is done in hardware with a large parallel array of product and sum components: https://en.wikipedia.org/wiki/Dadda_multiplier https://en.wikipedia.org/wiki/Dadda_multiplier Pipelining, as mentioned in a sibling comment, is used to increase throughput.