1.4 存储程序计算机
本书将相当详细地介绍两种高性能计算机：ARM系列计算机和Intel IA-64体系结构的计算机。但本节并不会将计算机视作一种既定事实，直接描述它的结构，而是会从概念上介绍计算机是如何设计的。因此本节将通过提出一个问题并分析解决这个问题需要哪些东西，来介绍一个非常简单的计算机的结构。尽管这个问题非常简单，但它却展示了一个真正的程序所要完成的操作以及指令序列的概念。本节将要设计的用来解决问题的计算机就是真正的存储程序计算机的一个初始版本。
1.4.1 问题描述
请考虑图1-7中的十进制数串23277366664792221。正如读者所看到的那样，其中有一些值相同的数字连续出现（例如连续的2个7、4个6和3个2）。我们的问题十分简单：找出最大游程，即同一个数字连续出现的最大次数。为了简化问题，假设数串的长度大于3。
从图1-7中可以很快看出结果应为4，因为这一串数字中有4个连续的6，而连续的7只有2个，连续的2则只有3个。我们将设计一台计算机来处理图1-7中的数串，它每次读一个数，并告诉我们最大游程是多少。
1.4.2 解决方法
如果我们从数串的左边开始逐个检查数字，在任何一个位置，我们都会得到以下两个结果之一：要么这个数与前一个相同，序列还在增长；要么这个数与上一个不同，前一个序列结束，一个新的序列开始。为了强调这一点，图1-7中用带阴影的圆角矩形标出了所有至少含有两个数的序列。
图1-8中的状态图可以帮我们解决这个问题。在任一时刻，某个系统都会处于几种可能的状态之一。例如，人要么睡着了，要么醒着；飞机则可能处于以下3种状态之一：爬升、降落或水平飞行。对于一个数字系统，当一个特定的事件（如时钟脉冲）发生时，它将从一个状态转换为另外一个状态。图1-8中，每当从数串中读出一个新的元素，都会发生状态转换。
图1-8中有两个状态，分别是“在同一序列中”和“不在同一序列中”。处于状态“在同一序列中”的条件是当发现连续的两个或更多的数字都具有相同的值时。如果处于状态“不在同一序列中”，且新的数与前一个数不同，则会依然维持当前状态“不在同一序列中”不变。如果新读出的数与上一个数相同，则状态将转换为“在同一序列中”，因为此时已经处于一个序列的第二个位置。只要每个新读出的数都与前一个相同，每次状态转换后都会维持“在同一序列中”的状态不变。只有当新读出的数与前一个不同时，状态才会被转换为“不在同一序列中”。
图1-9列出了一个接一个地读入图1-7中数串的数字后系统状态的转换情况。正如读者所看到的那样，状态的改变会发生在序列的第二个数字或结束序列的那个数字上。
表1-1则将这些数字组织成一种更容易理解的形式。最上面一行是每个数字在数串S中的位置或地址，下一行是串S中这个数字的值。例如，第11个元素的值是4。第三行则是当前序列中数的值；这一行的第一个元素是？，因为此时上一个元素的值是未知的。显然，第三行每个元素的值与第二行前一个元素的值相同。
让我们从数串的左边开始，逐个检查每个数字。我们每次读入一个新的数字，并问自己，“我们是否找到了一个新的序列？”如果此时正好处于一个序列的开始，那么这个序列的长度被置为1。如果这个数字是当前序列的一部分，则当前序列的长度增加1。现在我们遍历数串中的每个数字，并将每个数字对应的序列长度记录在表1-2中。序列长度在1～4之间变化。请注意，表1-2中“当前序列数值”这一行记录的是检查新元素之前的数值。
每当一个新的序列开始时，我们都会判断上一个序列是否比目前为止最长的序列还长。表1-3通过增加新的一行记录目前最大序列的长度来说明这是如何实现的。可以看到，当处理完数串最右边的第17个元素后，所记录的最大序列长度为4。注意，这个问题假定串的长度是已知的，处理过程何时停止也是已知的。如果不知道这些，那么就必须知道最后一个数是什么，显然它必须是唯一的。
1.4.3 构造一个算法
下一步是设计一个算法，告诉我们如何清楚明确地解决这个问题。遍历数串的时候，必须跟踪一些信息。当然，这些信息分别对应于表1-3中的各行。为方便起见，我们通过下面的符号名引用这些信息。
下面的伪码描述了解决这个问题所必需的操作。伪码的开始部分是初始化操作，它们仅被执行一次，而REPEAT…UNTIL所定义的重复操作加阴影表示。为简便起见，此处省去了索引变量i，用“第一个数”或“下一个数”表示各个数字，而没有用digit(i)或digit(i+1)。
上面的伪码使用了两个在很多高级语言中都能见到的结构：5～13行的REPEAT…UNTIL结构和IF…THEN…ELSE结构。REPEAT…UNTIL用于将一个动作执行一次或重复多次，IF…THEN…ELSE则从两个可能的动作中选择一个来执行。IF…THEN…ELSE是数字计算机的关键操作，本书会以多种方式多次用到这个结构。读者还会看到它是如何在硬件层实现的，它在几种不同的计算机上是如何表示的，它怎样给现代计算机的性能带来负面影响，一些计算机如何试图在它实际完成之前猜测其结果，以及一些计算机如何试图使用谓词操作完全避免它的出现。
1.4.4 计算机需要通过什么来解决问题
我们首先来看看解决这个问题时应进行哪些操作。由于1～13行的动作是顺序进行的，我们的计算机也必须能顺序地完成这些操作。细心的读者可能会发现我们选择顺序解决问题（每次一步）。这种方法既反映了人类的通常行为，也反映出计算机的实际发展。我们也可以采用另一种不同的方法，同时进行多个操作。我们设计出一种通用的问题求解机制，它能够很容易地被修改以便用于解决其他问题。我们也能设计一种只能解决这个问题的机制，但我们的目标是设计一台能够通过编程解决一系列问题的计算机。算法的前两行如下：
第1行从串中读出一个数，此时这个串必须保存在计算机存储器中的某处。符号名New_Digit指明了这个数在存储器中的位置。计算机必须确保它在任何需要使用当前序列的当前值的时候，都能访问到存储器的这个位置。
第2行是一个赋值操作，因为它将一个值赋给一个变量。同样，第3行和第4行也是赋值操作，它们分别将变量Current_Run_Length和Max_Run的值置为1。计算机必须能够完成从存储器中读出一个数，修改这个数并且将修改后的数写回存储器等操作。
第5行包含关键字REPEAT，它告诉我们这里是一组将被执行1次或多次的操作的起始位置。这组操作以第13行的关键字UNTIL结尾。
第7、8和10行说明了条件执行，即要执行的操作类型取决于测试结果。
第7行比较从串中读出的数值与当前序列的数值是否相同（即比较New_Digit与Current_Run_Value是否相同）。然后根据比较结果执行下面两个操作中的一个。一个操作由第8行关键字THEN后面的文字指定，另一个则由第9、10两行ELSE后的文字指定。第9和10两行包含在一对花括号{}中，说明执行时它们将被视作ELSE路径上的一个整体。
图1-10以流程图的方式描述了这一结构。
尽管这个问题相对简单，它却含有解决任一问题所需的全部元素：有将信息从一个位置传递到另一个的赋值操作；有加、减等算术运算；最后，还有根据计算结果（如比较）从两个候选动作中选择一个的操作。
计算机解决问题所需元素并不比上面介绍的内容多。可以说计算机体系结构就是更加快速、高效地实现我们所描述的各种操作类型。
在继续介绍计算机的设计之前，我们必须简要浏览一下保存程序和程序所用数据的存储系统。
1.4.5 存储器
人类的记忆是一种奇怪的、不精确的东西。一个事件会触发一次对某个被我们称为记忆的数据元素的回忆或检索。这里的事件也许是某人问你的一个问题，也许是让你回想起发生在过去的某段插曲的东西。通常我们只记得其中的一部分，甚至它还是错误的。人类是通过将某个事件与所保存的信息相匹配而查找或访问记忆的。也就是说，我们的记忆是联想的，因为我们总是将一段记忆与另一段联系在一起。计算机的存储器则完全不同，最好将它视作一个存放信息的表格或目录。
图1-11描述了程序怎样找出保存在一个假想存储器中的数串的最大序列长度。必须强调的是，这个程序是概念上的而不是实际的，因为真正的计算机指令比其更加基础。这幅图叫作存储器映射，它展示了信息在存储器中的存放位置。它是存储器的一幅快照，因为它表示存储器在某个特定时刻的状态。存储器映射也包含程序使用的变量和数字串。前面谈到过，存储程序计算机会将指令、变量和常量全部保存在同一个存储器内。
图1-11说明存储器中的每个位置要么保存了指令要么保存了数据元素。第一列中的数字0～37为地址，代表了数据元素和指令在存储器内的存放位置（地址从0而不是1开始，因为0是一个合法的标识符）。程序位于地址0～16的位置，变量位于地址17～20的位置，而数据（串）位于地址21～37的位置。可以将计算机的存储器视作一个数据元素的表格——每个元素的位置就是它的地址。例如，地址为3的存储单元保存了指令“将Max_Run置为1”而地址为20的存储单元保存了元素Max_Run的值。17行及其后面的各行使用了粗体字，表明它们保存了变量以及要处理的数串。
千万不要以为图1-11中的程序是真实的。为了简便起见，我们不得不省略了一些细节。例如，我们在地址10处放置了一条跳转指令，它告诉计算机忽略地址11和12处的指令，直接执行地址13的指令。这是必需的，因为如果执行了分支的THEN部分，那么必须忽略掉它的ELSE部分。此处还说明了怎样用符号Memory(i)来访问每个数字，它表示存储器的第i个单元。i的值被初始化为21，并且循环在i等于37时结束。
图1-12描述了存储系统的组成。处理器将一个放在地址总线上的地址以及一个用于选择读操作或写操作（它们有时也被称作读或写周期）的控制信号发送给存储器。在读周期中，存储器将数据放在数据总线上供CPU读取。在写周期中，放在数据总线上的数据被写入存储器。信息进入或离开存储器的位置（或计算机系统的其他功能部分）叫作端口。
尽管图1-12中的存储器是简化后的版本，它却准确地描述了将数据和指令连续存放的计算机存储器。一台真正的计算机会使用存储系统层次（每个层次都有可能采用不同的技术来实现）。这些层次包括保存频繁被访问数据的速度非常快的Cache、主存，以及速度非常慢的辅存，在这一层次中大量数据会一直保存在磁盘、光盘或DVD中，直到使用时才会被调入主存。
由于使用文字描述计算机的操作很不方便，下面介绍一个概念寄存器传输语言（Register Transfer Language, RTL），使用RTL可以更加容易地定义计算机内发生的操作。