C++ 被视为冯·诺依曼编程语言吗?

2023-12-28

期限冯诺依曼语言 https://en.wikipedia.org/wiki/Von_Neumann_programming_languages适用于其计算模型基于的编程语言冯·诺依曼计算机体系结构 https://en.wikipedia.org/wiki/Von_Neumann_architecture.

  • C++ 是否被视为冯·诺依曼语言,或者如果不是(例如,由于异步执行和线程的出现)它是否曾被视为冯·诺依曼语言?
  • 是否存在 C++ 的计算模型/抽象机所基于的体系结构,因此可以将其归类为该体系结构的语言?

TL:DR: C++ 抽象机是一种PRAM(并行随机存取机) https://en.wikipedia.org/wiki/Parallel_random-access_machine.


来自冯诺依曼语言 https://en.wikipedia.org/wiki/Von_Neumann_programming_languages您链接的维基百科文章:

许多广泛使用的编程语言,例如 C、C++ 和 Javaceased通过以线程的形式添加对并行处理的支持来严格遵循冯·诺依曼的要求。

Cease描述了从存在到不存在的转变。所以是的,在 C++11 添加线程之前,C++ 是strictly根据维基百科,冯·诺依曼语言。 (而且它基本上仍然是一种 VN 语言;让多个线程共享相同的地址空间并不会从根本上改变 C++ 的工作方式。)

在这种情况下,冯·诺依曼架构的有趣之处在于:

  • 拥有可寻址 RAM,允许随时有效访问(模缓存/分页)任何对象
  • 将程序存储在 RAM 中:函数指针是可能且高效的,无需解释器
  • 有一个程序计数器,可逐步执行存储程序中的指令:自然模型是一种一次只做一件事的命令式编程语言。这是非常基本的,以至于很容易忘记它不是唯一的模型! (与 FPGA 或 ASIC 或所有门可能在每个时钟周期并行执行某些操作的东西相比。或者 MIMD GPU,其中您编写的计算“内核”可能并行地运行所有数据,而无需隐式排序每个数据的顺序元素被处理。或者计算内存 https://en.wikipedia.org/wiki/Computational_RAM:将 ALU 放入内存芯片中以绕过冯·诺依曼瓶颈)

不过,我不知道为什么 wiki 文章提到了自修改代码;与大多数语言一样,ISO C++ 没有对此进行标准化,并且与提前编译完全兼容分割总线/分割地址空间哈佛架构 https://en.wikipedia.org/wiki/Harvard_architecture. (No eval或任何其他需要解释器或 JIT 的东西。)或者在普通 CPU 上(冯·诺依曼 https://en.wikipedia.org/wiki/Von_Neumann_architecture),严格的W^X内存保护并且从不使用mprotect将页面权限从可写更改为可执行。

当然最真实的C++实现do提供定义良好的方法将机器代码写入缓冲区并转换为函数指针,作为扩展。 (例如 GNU C/C++__builtin___clear_cache(start, end)因 I-cache 同步而命名,但其定义是为了能够安全地将数据作为函数调用。死存储消除优化也是如此,因此即使在具有一致 I 缓存的 x86 上,如果没有它,代码也可能会中断。)实现可以扩展 ISO C++ 以利用冯·诺依曼架构的这一特性; ISO C++ 有意限制范围,以允许操作系统和类似内容之间存在差异。

请注意,成为冯·诺依曼确实not严格暗示支持间接寻址模式。一些早期的 CPU 没有,并且需要自修改代码(重写指令中硬编码的地址)来实现我们现在使用间接寻址的功能。

另请注意,约翰·冯·诺依曼是一位非常著名的人物,他的名字与许多基本事物相关。冯·诺依曼建筑(与哈佛相对)的一些内涵并不真正适用于所有情况。例如“冯·诺依曼语言”这个术语不太关心冯·诺依曼与哈佛;它关心带有程序计数器的存储程序与元胞自动机或图灵机(带有真实磁带)之类的东西。通过使用单独的总线(或只是分割缓存)来获取指令(哈佛)来获得额外的带宽只是一种性能优化,而不是根本性的改变。


抽象机器模型/计算模型到底是什么?

首先,有一些计算模型 https://en.wikipedia.org/wiki/Model_of_computation那是weaker比图灵机,像有限状态机 https://en.wikipedia.org/wiki/Finite-state_machine。还有非顺序计算模型,例如元胞自动机(康威的生命游戏) https://en.wikipedia.org/wiki/Cellular_automaton,其中每个“步骤”并行发生多个事情。

The 图灵机 https://en.wikipedia.org/wiki/Turing_machine是最广为人知的(并且数学上简单的)顺序抽象机 https://en.wikipedia.org/wiki/Abstract_machine这是我们所知道的“强大”程度。没有任何形式的绝对内存寻址,只是磁带上的相对移动,它自然提供了无限的存储。这很重要,并且在某些方面使得所有其他类型的抽象机器与真实的 CPU 非常不同。请记住,这些计算模型用于理论的计算机科学,而不是工程学。有限的内存或性能等问题与可计算的内容无关理论上,仅在实践中。

如果你可以在图灵机上计算某些东西,你就可以在任何其他图灵完备的计算模型上计算它(根据定义),也许使用更简单的程序,也可能不使用。图灵机不太好编程,或者至少不太好编程不同的来自任何真实 CPU 的汇编语言。最值得注意的是,内存不是随机访问的。而且他们无法轻松地对并行计算/算法进行建模。 (如果你想抽象地证明一个算法的事情,那么为某种抽象机实现它可能是一件好事。)

证明抽象机需要具备哪些功能才能实现这一点也可能很有趣be图灵完备,所以这是开发更多它们的另一个动机。

还有许多其他在可计算性方面是等效的。这内存机型号 https://en.wikipedia.org/wiki/Random-access_machine最像现实世界中具有内存阵列的 CPU。但作为一个简单的抽象机器,它不关心寄存器。事实上,只是为了让事情变得更混乱,它将其存储单元称为数组寄存器。 RAM 机器支持间接寻址,因此与现实世界 CPU 的正确类比肯定是内存,而不是 CPU 寄存器。 (寄存器的数量是无限的,每个寄存器的大小都是无限的。地址永远持续下去,每个“寄存器”都需要能够保存一个指针。) RAM 机器可以是哈佛:程序存储在单独的有限状态部分中机器。将其视为具有内存间接寻址模式的机器,以便您可以将“变量”保留在已知位置,并使用其中一些作为指向无限大小数据结构的指针。

抽象 RAM 机的程序 https://en.wikipedia.org/wiki/Random-access_machine#Examples_of_models看起来像汇编语言,带有 load/add/jnz 以及您希望它具有的任何其他指令选择。操作数可以是立即数或寄存器号(普通人称之为绝对地址)。或者,如果模型有一个累加器,那么您就有一个带有累加器的加载/存储机器,就像真正的 CPU 一样。

如果您想知道为什么像 MIPS 这样的“3 地址”机器被称为而不是 3 操作数,它可能是 1。因为指令编码需要通过冯·诺依曼瓶颈的空间/I-fetch 带宽 3explicit操作数位置(寄存器编号)和2.因为在RAM抽象机中,操作数是内存地址=寄存器编号。


C++ 不可能是图灵完备的:指针的大小是有限的。

当然C++有huge与 CS 抽象机模型的区别:C++ 要求每种类型都有一个有限的编译时间常数sizeof,所以 C++can't如果包含无限存储要求,则为图灵完备。一切都在C实际上是图灵完备的吗? https://cs.stackexchange.com/questions/60965/is-c-actually-turing-completecs.SE 也适用于 C++:类型具有固定宽度的要求是无限存储的一个障碍。也可以看看https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded


那么计算机科学抽象机很愚蠢,那么 C++ 抽象机呢?

它们当然有它们的目的,但是如果我们了解一点,我们可以谈论更多关于 C++ 以及它假设的机器类型的更有趣的东西不那么抽象并谈论机器可以做什么有效率的。一旦我们谈论有限机器和性能,这些差异就变得相关了。

首先,完全运行 C++,其次,在没有巨大和/或不可接受的性能开销的情况下运行。 (例如,硬件需要相当直接地支持指针,可能不需要使用将指针值存储到使用它的每个加载/存储指令中的自修改代码。这在线程是其中一部分的 C++11 中不起作用语言:相同的代码可以同时操作 2 个不同的指针。)

我们可以更详细地了解 ISO C++ 标准所假设的计算模型,该模型描述了该语言如何根据抽象机上发生的情况工作。真实的实现需要在真实的硬件上运行代码,“就像”抽象机正在执行 C++ 源代码一样,再现任何/所有可观察的行为(无需调用 UB 即可由程序的其他部分观察到)。

C/C++ 有内存和指针,所以它绝对是一种 RAM 机器。

或者说这些天,a 并行随机存取机 https://en.wikipedia.org/wiki/Parallel_random-access_machine,将共享内存添加到 RAM 模型,并为每个线程提供自己的程序计数器。鉴于std::atomic<>发布序列使all先前的操作对其他线程可见,同步的“建立发生在关系”模型基于coherent共享内存。在需要手动触发同步/刷新的东西之上模拟它对于性能来说是可怕的。 (非常聪明的优化可能会证明何时可以延迟,因此并非每个发布存储都会受到影响,但 seq-cst 可能会很糟糕。seq-cst 必须建立所有线程都同意的全局操作顺序;这很难,除非商店同时对所有其他线程可见。)

但请注意,在 C++ 中,实际的同时访问是 UB,除非您使用atomic<T>. This 允许优化器自由使用CPU寄存器 https://electronics.stackexchange.com/questions/387181/mcu-programming-c-o2-optimization-breaks-while-loop/387478#387478对于本地变量、临时变量、甚至全局变量,无需将寄存器暴露为语言功能。UB 允许优化 http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html一般来说;这就是为什么现代 C/C++ 实现是not可移植的汇编语言。

历史的registerC/C++ 中的关键字意味着变量不能获取其地址,因此即使是非优化编译器也可以将其保存在 CPU 寄存器中,而不是内存中。我们谈论的是CPU寄存器,而不是计算机科学RAM机器“寄存器=可寻址内存位置”。 (喜欢rax..rsp/r8..r15在 x86 上,或r0..r31在 MIPS 上)。现代编译器会进行转义分析,并自然地将局部变量正常保留在寄存器中,除非必须溢出它们。其他类型的 CPU 寄存器也是可能的,例如类似于 x87 FP 寄存器的寄存器堆栈。无论如何,register关键字的存在是为了优化这种类型的机器。但也不排除在没有寄存器、只有内存-内存指令的机器上运行。

C++ 设计为在具有 CPU 寄存器的冯·诺依曼机器上良好运行,但是 C++ 抽象机(标准用来定义语言)不允许将数据作为代码执行,也不允许对寄存器进行任何描述。不过,每个 C++ 线程确实有自己的执行上下文,并且对 PRAM 线程/核心进行建模,每个线程/核心都有自己的程序计数器和调用堆栈(或实现用于自动存储和确定返回位置的任何实现)。对于 CPU 寄存器,它们是每个线程私有的。

所有现实世界的 CPU 都是随机存取机 https://en.wikipedia.org/wiki/Random-access_machine,并将 CPU 寄存器与可寻址/可索引 RAM 分开。即使只能使用单个累加器寄存器进行计算的 CPU 通常也至少有一个指针或索引寄存器,至少允许一些有限的数组索引。至少所有可以作为 C 编译器目标运行良好的 CPU。

如果没有寄存器,每个机器指令编码都需要所有操作数的绝对内存地址。 (也许像 6502 一样,其中“零页”(内存的低 256 字节)是特殊的,并且存在使用零页中的字作为索引或指针的寻址模式,以允许 16 位指针,而无需任何 16 位指针。位架构寄存器。或者类似的东西。)参见为什么 C 到 Z80 编译器会生成糟糕的代码?关于RetroComputing.SE https://retrocomputing.stackexchange.com/questions/6095/why-do-c-to-z80-compilers-produce-poor-code有关现实世界 8 位 CPU 的一些有趣的内容,其中完全兼容的 C 实现(支持递归和重入)的实现成本相当昂贵。速度缓慢的主要原因是 6502 / Z80 系统太小,无法承载优化编译器。但即使是假设的现代优化交叉编译器(如 gcc 或 LLVM 后端)也会在某些方面遇到困难。另请参阅最近的答案什么是未使用的内存地址? https://stackoverflow.com/questions/52781571/what-is-an-unused-memory-address/58315206#583152066502 的零页索引寻址模式的一个很好的解释:来自内存中绝对 8 位地址的 16 位指针 + 8 位寄存器。

机器without间接寻址根本无法轻松支持数组索引、链表,并且绝对不能支持作为第一类对象的指针变量。 (反正效率不高)


什么是有效的real机器 -> 哪些习语是自然的

C 的大部分早期历史都在PDP-11 https://en.wikipedia.org/wiki/PDP-11,这是一个普通的内存+寄存器机器,其中任何寄存器都可以用作指针。当需要溢出时,自动存储映射到寄存器或调用堆栈上的空间。内存是一个平面的字节数组(或块)char),没有分段。

数组索引只是根据指针算术定义的,而不是它自己的东西,也许是因为 PDP-11 可以有效地做到这一点:任何寄存器都可以保存地址并被取消引用。 (相对于一些只有几个特殊寄存器的指针宽度的机器,其余的更窄。这在 8 位机器上很常见,但像 PDP-11 这样的早期 16 位机器没有足够的 RAM,以至于一个 16 位寄存器对于地址来说就足够了)。

请参阅丹尼斯·里奇的文章C语言的发展 https://www.bell-labs.com/usr/dmr/www/chist.html了解更多历史;C 在 PDP-7 Unix 上由 B 发展而来。 (第一个 Unix 是用 PDP-7 asm 编写的)。我对 PDP-7 不太了解,但显然 BCPL 和 B 也使用只是整数的指针,而数组是基于指针算术的。

PDP-7 是一种 18 位字可寻址 ISA https://en.wikipedia.org/wiki/PDP-7。这可能就是B没有的原因char类型。但它的寄存器足够宽,可以容纳指针,因此它自然支持 B 和 C 的指针模型(指针并不真正特殊,您可以复制它们并取消引用它们,并且可以获取任何内容的地址)。因此,平坦的内存模型,没有像分段机器或某些具有零页的 8 位微处理器那样的“特殊”内存区域。

像 C99 VLA(和无限大小的局部变量)和无限重入和递归之类的东西意味着函数局部变量上下文的调用堆栈或其他分配机制(也称为使用堆栈指针的普通计算机上的堆栈帧。)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

C++ 被视为冯·诺依曼编程语言吗? 的相关文章

随机推荐