C ++是否被视为Von Neumann编程语言?

101010

术语“冯·诺依曼语言”适用于其计算模型基于冯·诺依曼计算机体系结构的编程语言

在此处输入图片说明

  • C ++是否被视为Von Neumann语言,或者如果不是(例如,由于线程的出现导致异步执行),是否曾经被视为Von Neumann语言?
  • 是否存在C ++的计算模型/抽象机所基于的体系结构,因此可以归类为该体系结构的语言?
彼得·科德斯

TL:DR:C ++抽象机是PRAM(并行随机存取机)的一种


冯·诺依曼语言维基百科文章中,您链接到:

通过广泛地支持线程形式的并行处理,许多严格使用的编程语言(例如C,C ++和Java)已不再严格地由von Neumann所主导。

停止描述了从存在到不存在的过渡。是的,在Wikipedia看来,在C ++ 11添加线程之前,C ++严格来说是冯·诺依曼语言。(并且在基本上仍然是VN语言之后;让多个线程共享同一地址空间并不会从根本上改变C ++的工作方式。)

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

  • 完全具有可寻址的RAM,从而可以随时有效地访问(对象高速缓存/分页)
  • 将程序存储在RAM中:功能指针是可能且高效的,而无需解释器
  • 有一个程序计数器可以逐步执行存储程序中的指令:自然模型是一种命令式编程语言,它一次只能执行一项操作这是如此基础,很容易忘记它不是唯一的模型!(与FPGA或ASIC或在每个时钟周期内所有门可能并行执行某事的事物。或MIMD GPU上,您编写的计算“内核”可能在所有数据上并行运行,而无需隐式排序每个数据的顺序处理元素。或计算RAM:将ALU放入存储芯片中以绕过冯·诺依曼瓶颈

IDK为什么Wiki文章中会提及自修改代码;像大多数语言一样,ISO C ++对此未进行标准化,并且与用于split-bus / split-address-space-harvard体系结构的提前编译完全兼容(否eval或需要解释器或JIT的其他任何方法。)或在常规CPU(Von Neumann)上,使用严格的W ^ X内存保护,并且从未使用mprotect过将页面权限从可写更改为可执行文件。

当然,大多数真正的C ++实现确实提供了明确定义的方法,可以将机器代码写入缓冲区并转换为扩展函数指针。(例如,GNU C / C ++的名称__builtin___clear_cache(start, end)是为I-cache同步而命名的,但其定义是为了确保可以安全地将数据作为函数调用数据。同时还优化了死存储消除,因此即使在x86上,如果没有它,代码也可能会中断因此实现可以扩展ISO C ++以利用Von Neumann体系结构的这一功能故意限制ISO C ++的范围,以允许OS和类似内容之间的差异。

请注意,是冯·诺依曼并没有严格地暗示支持间接寻址模式。一些早期的CPU不需要,并且自修改代码(以重写指令中的硬编码地址)对于实现我们现在使用间接处理的内容是必需的。

还要注意,约翰·冯·诺伊曼(John Von Neumann)是一个非常有名的人,他的名字与很多基本事物联系在一起冯·诺依曼建筑学的某些内涵(与哈佛相反)并不是在所有情况下都真正相关。例如,“冯·诺依曼语言”一词不太在乎冯·诺依曼与哈佛。它关心的是带有程序计数器的存储程序,而不是诸如Cellular Automata或Turing机器(带有真实磁带)之类的东西通过使用单独的总线(或只是拆分的缓存)来获取指令(哈佛)来获得额外的带宽只是性能优化,而不是根本的改变。


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

首先,有些计算模型比图灵机(例如有限状态机)也有非顺序计算模型,例如Cellular Automata(康威的生命游戏),其中每个“步骤”并行发生多件事。

图灵机是最广为人知的(和数学简单)的顺序抽象机是“强”,因为我们知道如何做。如果没有任何绝对的内存寻址方式,只是磁带上的相对移动,它自然就可以提供无限的存储空间。这很重要,在某种程度上使所有其他种类的抽象机与实际CPU完全不同。请记住,这些计算模型用于理论计算机科学,而不是工程学。诸如有限的内存或性能之类的问题与理论上可计算的内容无关,只有在实践中才有意义。

如果您可以在Turing机器上进行计算,则可以在其他任何Turing完整的计算模型(按定义)上进行计算,也许可以使用更简单的程序,也可以不用。图灵机的编程不是很好,或者对于任何实际的CPU至少与汇编语言都没有很大的区别最值得注意的是,内存不是随机访问的。而且他们无法轻松地为并行计算/算法建模。(如果您想以抽象的方式证明有关算法的内容,那么为某种抽象机实现该算法的实现可能是一件好事。)

这也是潜在的有趣证明什么功能的抽象的机器需要有以图灵完整,所以这是开发更多的人的另一个动机。

在可计算性方面,还有许多其他方面是等效的。内存的机器模型是最喜欢的是有记忆的阵列现实世界的CPU。但是作为一台简单的抽象机,它不会为寄存器带来麻烦。实际上,只是为了使事情变得更加混乱,它将其存储单元称为寄存器数组。RAM机支持间接寻址,因此,与实际CPU的正确比喻绝对是内存,而不是CPU寄存器。(并且有无数个寄存器,每个寄存器的大小都是无限制的。地址一直在不断发展,每个“寄存器”都必须能够容纳一个指针。)RAM机可以是哈佛的:程序存储在独立的有限状态部分中机器。可以将其视为具有内存间接寻址模式的计算机,这样您就可以将“变量”保留在已知位置,并将其中一些变量用作指向无限制大小的数据结构的指针。

抽象RAM机器的程序看起来像汇编语言,带有load / add / jnz以及您希望它具有的其他指令选择。操作数可以是立即数或寄存器号(普通人称其为绝对地址)。或者,如果模型具有累加器,则您的装载/存储计算机带有累加器,更像是真正的CPU。

如果您想知道为什么调用像MIPS这样的“ 3地址”机器而不是3操作数,它可能是1。因为指令编码需要通过Von Neumann瓶颈的3个显式操作数位置的空间/ I提取带宽(寄存器2),因为在RAM抽象机中,操作数是内存地址=寄存器号。


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

当然,C ++与CS抽象机模型很大的不同:C ++要求每种类型都具有一个编译时常量sizeof,因此,如果您包含infinite-storage要求,那么C ++不可能是图灵完备的在一切都为C实际上图灵完备?在cs.SE上也适用于C ++:类型具有固定宽度的要求是无限存储的首选。另请参阅https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded


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

它们当然有其目的,但是关于C ++,还有很多有趣的事情,如果我们不那么抽象,并且谈论一台机器可以有效地工作,那么它可以假设什么样的机器一旦我们讨论了有限机器的机器和性能,这些差异就变得很重要。

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

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

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

或近些年来,一台并行随机存取机,向RAM模型添加共享内存,并为每个线程提供自己的程序计数器。鉴于std::atomic<>释放顺序使所有先前的操作对其他线程可见,因此同步的“建立先于关系”模型基于连贯的共享内存。在需要手动触发同步/刷新的东西上进行仿真对于性能而言是可怕的。(非常聪明的优化可能会证明何时可以延迟执行该延迟,因此并非每个发布存储都必须受苦,但是seq-cst可能会很可怕。seq-cst必须建立所有线程都同意的全局操作顺序;这很难做到,除非同时所有其他线程都可以看到一个存储区。)

但请注意,在C ++中,除非同时使用,否则实际的同时访问是UB atomic<T>使优化器可以将CPU寄存器自由地用于本地,临时甚至全局变量,而无需将寄存器公开为语言功能。UB通常允许优化这就是为什么现代C / C ++实现不是可移植的汇编语言。

registerC / C ++中的history关键字表示变量不能使用其地址,因此,即使是非优化的编译器也可以将其保存在CPU寄存器中,而不是内存中。我们在谈论的是CPU寄存器,而不是计算机科学RAM机器“寄存器=可寻址的内存位置”。(类似于rax..rsp/r8..r15x86或r0..r31MIPS)。现代的编译器会进行转义分析,并自然将本地变量正常保留在寄存器中,除非它们不得不溢出它们。其他类型的CPU寄存器也是可能的,例如x87 FP寄存器之类的寄存器堆栈。无论如何,register关键字的存在是为了针对这种类型的机器进行优化。但这并不排除在没有寄存器,只有内存指令的计算机上运行。

C ++被设计为可以在带有CPU寄存器的Von Neumann机器上很好地运行,但是C ++抽象机器(该标准用于定义语言)不允许将数据作为代码执行,也不能说任何有关寄存器的内容。但是,每个C ++线程的确有其自己的执行上下文,并且该模型对PRAM线程/内核进行了建模,每个线程都有自己的程序计数器和调用堆栈(或任何用于自动存储并确定返回位置的实现)。对于CPU寄存器,它们是每个线程专用的。

现实世界中所有的CPU都是随机存取机,并且CPU寄存器与可寻址/可索引RAM分开。即使是只能使用单个累加器寄存器进行计算的CPU,通常也至少具有一个指针或索引寄存器,这至少允许一些有限的数组索引。至少所有可以很好地用作C编译器目标的CPU。

没有寄存器,每种机器指令编码将需要所有操作数的绝对内存地址。(也许就像6502一样,其中“零页”,低256字节的内存是特殊的,并且有些寻址模式使用零页中的一个字作为索引或指针,以允许16位指针不带任何16位体系结构寄存器。或类似的东西。)请参阅C到Z80编译器为什么生成不良代码?在RetroComputing.SE对于一些有关实际8位CPU的有趣东西,其中完全兼容的C实现(支持递归和重入)的实现成本非常高。许多缓慢之处是6502 / Z80系统太小,无法托管优化的编译器。但是,即使是假设的现代优化交叉编译器(例如gcc或LLVM后端)在某些方面也很难。另请参阅关于什么是未使用的内存地址的最新答案对于6502的零页索引寻址模式的一个很好的解释:来自内存+ 8位寄存器的绝对8位地址的16位指针。

根本没有间接寻址的机器无法轻易地支持数组索引,链接列表,并且绝对不能将指针变量作为一流对象。(反正效率不高)


实际机器上什么有效->什么习惯是自然的

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

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

有关更多历史记录,请参见Dennis Ritchie的文章C语言的发展C在PDP-7 Unix上由B成长而来(第一个Unix是用PDP-7 asm编写的)。我对PDP-7不太了解,但是显然BCPL和B也使用只是整数的指针,并且数组基于指针算术。

PDP-7是一个18位字可寻址的ISA这可能就是为什么B没有char类型的原因。但是它的寄存器足够宽以容纳指针,因此它自然支持B和C的指针模型(指针并不是真正的特殊,您可以在它们周围复制并取消引用它们,并且可以使用任何地址)。因此,内存模型是平面的,没有像分段计算机或页面为零的8位微控制器上那样的“特殊”内存区域。

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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章