3 ms·

This is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. Isn't there a trivial counterexample where the bandwidth is d

by YZF 2y ago

This is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. Isn't there a trivial counterexample where the bandwidth is divided by the number of processors and each processor gets a timeslot? Processors, despite being a distributed system (well really every ASIC is), don't typically suffer from your classical distributed systems style issues because they have no failures, or rather they only have certain catastrophic failure modes that are low probability and well controlled for. Your typical distributed system to contrast has constant failures.

Animats 2y ago
> This is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. See [1]. This was a very real problem in early multiprocessor computer design. [1] https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 https://en.wikipedia.org/wiki/Arbiter_%28electronics%29
- fanf2 2y ago
  Are there many (or even any) multi-drop buses in modern computers? I get the impression that these days almost everything is point-to-point links. But I know less about what’s happening on silicon. I have seen talk of crossbar interconnects on microcontrollers, which (aiui) are more active, unlike passive buses?
  - Animats 2y ago
    Memory controllers with more than one port have an internal arbiter. The ports are connected to various CPUs, GPUs, and I/O devices. Something has to sequence requests to the memory interface. Memory controllers used to be separate chips, but since about 2008 they're usually on the CPU die. Memory arbiters are where atomic operations on memory are actually implemented.
  - avianlyric 2y ago
    I2C buses still tend to turn up in modern computers for running various low level components. Stuff like allowing the CPU to talk to power management systems, controlling fan speeds, RGB lights etc I don’t think there are any high bandwidth multi-drop busses anymore. Electrically multi-drop busses don’t make it easy to ensure the needed signal integrity for high speed busses.
rcxdude 2y ago
It's more to do with the underlying electronics: digital is an abstraction, everything is analog underneath, and logic gates and registers are actually just very non-linear analog circuits. What this means is that it's always in principle possible for an asynchronous edge (i.e. one that is not aligned to the other edges in the system) to be arbitrarily non-determinate: never actually being decided as a 1 or a 0 as it propagates through the digital circuit. This isn't an entirely theoretical issue, either: it can and will cause very strange behaviour in a digital system because a marginal or metastable value can be interpreted differently by different parts of the circuit that should be seeing the same value. It's possible in practice to push the chance of this happening extremely low, but it comes at the cost of latency: you need to spend more time to allow the circuit to actually settle into one state or the other. Within a fully synchronous system, it's possible to avoid this, though. But most multi-processor systems are not synchronous.
- londons_explore 2y ago
  > But most multi-processor systems are not synchronous. Is this actually true? A modern AMD or Intel CPU doesn't have one quartz crystal per core, so therefore all per-core clocks have to be derived from one clock source, meaning the relationship between all the clock frequencies and phases is deterministic, even if not specced in the datasheet.
  - YZF 2y ago
    There would be a single clock typically but OP is right in the sense that as the signal propagates through the system you can get nondeterministic effects: https://en.wikipedia.org/wiki/Metastability_(electronics) https://en.wikipedia.org/wiki/Metastability_(electronics) In practice the probability of that is just driven low enough that it's not an issue.
  - rcxdude 2y ago
    Multi-core isn't the same as multi-processor, and in practice while they are derived from the same reference, dynamic per-core clock scaling makes it pretty asynchronous, to say nothing of the I/O paths between the many independently clocked parts of a modern computer.
imtringued 2y ago
Modern processors have "packet" (nowhere near as complex as ethernet/IP/TCP) based Network On Chip interconnects based with packet routing. Processors suffer from the classical distributed system style issues just the same, the difference is that as you said they tend to be more reliable and the configuration doesn't change at runtime, but another key aspect is that a lot of latency tradeoffs aren't as lethal due to the short distances within a chip. Accessing data that is kept in the cache of another processor only costs you 100ns at most and a lot of that overhead comes from time spent on the cache coherency protocol. Modern directory based cache coherency protocols are complicated beasts. Each processor core needs to be aware which processors have a copy of the cache line it is about to access, so that it can request exclusive write access to that cache line and mark every single one of those copies dirty upon modification. The way the distributed system problems manifest themselves on the higher levels is that cache coherency by itself doesn't get you correct software automatically. You still have to use synchronization primitives or atomics on the software level, because your registers are essentially stale read replicas. Compare and swap on the processor level is no different than compare and swap on mongodb.

by YZF 2y ago

Animats 2y ago

> This is the first time I'm hearing about the topic of arbitrating multiprocessor access to memory. See [1]. This was a very real problem in early multiprocessor computer design. [1] https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 https://en.wikipedia.org/wiki/Arbiter_%28electronics%29

fanf2 2y ago
Are there many (or even any) multi-drop buses in modern computers? I get the impression that these days almost everything is point-to-point links. But I know less about what’s happening on silicon. I have seen talk of crossbar interconnects on microcontrollers, which (aiui) are more active, unlike passive buses?
- Animats 2y ago
  Memory controllers with more than one port have an internal arbiter. The ports are connected to various CPUs, GPUs, and I/O devices. Something has to sequence requests to the memory interface. Memory controllers used to be separate chips, but since about 2008 they're usually on the CPU die. Memory arbiters are where atomic operations on memory are actually implemented.
- avianlyric 2y ago
  I2C buses still tend to turn up in modern computers for running various low level components. Stuff like allowing the CPU to talk to power management systems, controlling fan speeds, RGB lights etc I don’t think there are any high bandwidth multi-drop busses anymore. Electrically multi-drop busses don’t make it easy to ensure the needed signal integrity for high speed busses.

rcxdude 2y ago

It's more to do with the underlying electronics: digital is an abstraction, everything is analog underneath, and logic gates and registers are actually just very non-linear analog circuits. What this means is that it's always in principle possible for an asynchronous edge (i.e. one that is not aligned to the other edges in the system) to be arbitrarily non-determinate: never actually being decided as a 1 or a 0 as it propagates through the digital circuit. This isn't an entirely theoretical issue, either: it can and will cause very strange behaviour in a digital system because a marginal or metastable value can be interpreted differently by different parts of the circuit that should be seeing the same value. It's possible in practice to push the chance of this happening extremely low, but it comes at the cost of latency: you need to spend more time to allow the circuit to actually settle into one state or the other. Within a fully synchronous system, it's possible to avoid this, though. But most multi-processor systems are not synchronous.

londons_explore 2y ago
> But most multi-processor systems are not synchronous. Is this actually true? A modern AMD or Intel CPU doesn't have one quartz crystal per core, so therefore all per-core clocks have to be derived from one clock source, meaning the relationship between all the clock frequencies and phases is deterministic, even if not specced in the datasheet.
- YZF 2y ago
  There would be a single clock typically but OP is right in the sense that as the signal propagates through the system you can get nondeterministic effects: https://en.wikipedia.org/wiki/Metastability_(electronics) https://en.wikipedia.org/wiki/Metastability_(electronics) In practice the probability of that is just driven low enough that it's not an issue.
- rcxdude 2y ago
  Multi-core isn't the same as multi-processor, and in practice while they are derived from the same reference, dynamic per-core clock scaling makes it pretty asynchronous, to say nothing of the I/O paths between the many independently clocked parts of a modern computer.

imtringued 2y ago

Modern processors have "packet" (nowhere near as complex as ethernet/IP/TCP) based Network On Chip interconnects based with packet routing. Processors suffer from the classical distributed system style issues just the same, the difference is that as you said they tend to be more reliable and the configuration doesn't change at runtime, but another key aspect is that a lot of latency tradeoffs aren't as lethal due to the short distances within a chip. Accessing data that is kept in the cache of another processor only costs you 100ns at most and a lot of that overhead comes from time spent on the cache coherency protocol. Modern directory based cache coherency protocols are complicated beasts. Each processor core needs to be aware which processors have a copy of the cache line it is about to access, so that it can request exclusive write access to that cache line and mark every single one of those copies dirty upon modification. The way the distributed system problems manifest themselves on the higher levels is that cache coherency by itself doesn't get you correct software automatically. You still have to use synchronization primitives or atomics on the software level, because your registers are essentially stale read replicas. Compare and swap on the processor level is no different than compare and swap on mongodb.