松耦合并行处理器上DARYN模拟

为了详细分析DARYN算法的属性，我们在一个松耦合并行处理器ARMSTRONG[32]上对该算法进行模拟。这是个很合适的测试平台，因为它的结构——建立在特定通信协议基础上的并行处理器——和列车与车站计算机之间在地理上的分布状况极为相似，并行的列车和车站计算机正是通过特定的信息进行通信的。ARM-STRONG^[32]有68个高性能的MC68010（10MHz）处理器，它们在一个超立方体结构中通过高速通信线路连接。每个处理器可以同步或异步地执行应用程序。此外，独立处理器上的执行程序可以通过明确的、高层次的通信元进行通信。在这项研究中，某个给定的铁路网络上，每台车站计算机在ARMSTRONG中都表示成节点。两台车站计算机之间的信息渠道是通过ARMSTRONG上相应节点之间的软件协议来模拟的。在理想的情况下，人们希望系统中每台车载计算机都能表示成ARM-STRONG处理器，这就必须在车载计算机和列车目的车站的站台计算机之间动态地建立协议。同时，车载计算机和前一站的车站计算机建立的协议必须删除，因为很可能永远都不会再使用它。虽然在理论上ARMSTRONG支持协议的动态分配和重新分配，但是这样的分配结果往往是不可靠的，所以无法使用。在此研究中，车载计算机理论上是用迁徙过程表示的。当一列火车R_i停留在站A时，相应的车载计算机（对应于ARMSTRONG上相应的节点）与车站计算机的计算进程同步执行决策过程。当火车从A移到B时，上一节点的进程被禁用，车载计算机将各种重要参数以消息的形式传达给B。在B上，通过相应的ARMSTRONG节点，启动车站B计算机，同步执行一个新的可执行程序。车站计算机的计算进程是由R_i传达给B的参数决定的。于是，列车不断地在ARMSTRONG节点（对应列车行驶的站）上重复这种行为，直到到达目的地。也就是说，列车的参数一直在不断更新，并随着列车的运行，不断通过网络在节点间传送。这个模型的缺点是，车载计算机有可能无法通过独立、并行的ARMSTRONG处理器来模拟。此外，代表车站的节点必须将它的计算能力按车站和车载计算机分为两部分。ARMSTRONG节点的这种双重身份明显降低了DARYN算法的性能。理想模式下的DARYN应该是能在ARM-STRONG并行处理器上控制每列火车。

在每一个对应于铁路网中车站的ARMSTRONG节点上，都需要存储整个网络的完整信息。当一列火车到达该车站时，车载计算机程序就会读取这些信息。而每台车站计算机则完全了解系统中每条轨道的真正占用者，这是基于这样的假设：轨道布局的变化频率非常小，并且任何这类变化的信息都可以迅速地通过网络进行传播。车载计算机发出的轨道请求，最初传达到火车当前所在位置的车站计算机中。然后，该消息被传送到实际控制火车希望使用的那条轨道的车站计算机上。在收到两个或更多的轨道使用请求后，车站计算机要判断哪个是最早请求时间，并且批准与最早请求时间对应的那列火车的请求。此时，所有其他轨道使用请求都被拒绝。如果有不止一台车载计算机符合最低请求时间条件，车站计算机将任意批准它们其中一个的请求。

由于DARYN是异步的，因此每台车载计算机都有自己的时间计数器。最初，所有的车载计算机启动时，它们的时间计数器都初始化为0。随着模拟的进行，车载计算机会将计算火车请求的时间和火车移动的时间增加进来，火车在某条轨道上所花费的时间就等于该轨道长度除以火车的速度。因此，异步算法的优点就是能并行计算，同时简化了同步大型系统中由于存在大量火车所产生的复杂性。

在ARMSTRONG中，通信过程采用无闭塞基元。一旦建立了一个协议，数据在节点间的传送过程如下：发送节点通过ipc_send（information_path，data_1，data_2，…，data_n）命令将数据发送到接收节点。发送程序会立即从收到信息的操作系统获得响应，如果信息传送成功，发送节点会收到一个1，否则，就会收到0，意味着传送失败。接下来发送程序会再次尝试发送信息。由于该系统是异步的，接收节点可能不知道发送者发送数据的确切时间。每隔一段时间，系统就运行一次ipc_select（information_path）命令，检查数据是否一直沿着指定的路径传输。如果是，接收节点就可以通过ipc_receive（information_path，data_1，data_2，…，data_n）读到数据，否则，接收者就不能执行ipc_receive命令。ipc_select也是无闭塞的，也会立即得到正面或负面的响应。

为简化问题，将轨道放置在X（水平）和Y（垂直）方向，节点放置在长方形矩阵中，这确保了每列火车的轨道请求算法尽可能简单。每列火车首先通过计算X-Y坐标系中当前位置和最终目的地之差来确定它的轨道请求。如果Y方向离目的地的距离大于X方向，火车会试图在Y方向移动，从而接近最终目的地。类似地，如果X方向离目的地的距离大于Y方向，火车就会试图在X方向移动。就这样，火车找到合适的轨道请求后，将其提交给控制该轨道的相应的节点处理器。一旦收到确认或拒绝的回应，火车就会考虑下一步动作。如果火车请求得到批准，它会沿着批准的轨道移动。如果火车的请求被拒绝，它会重新计算第二个轨道选择，并再次提交请求。火车的第二选择是基于它试图移动的方向，而不是它的第一选择。这个过程一直持续到列车的某条轨道请求被批准为止。(www.xing528.com)

ARMSTRONG系统的仿真也是异步的，很有可能在同一时间从不同的节点发出两个或更多的信息，但是它们到达目的地的时间却有很大差异。这种现象导致在仿真中引入了“时间”问题，可以这样描述：假设，如图4.4中的铁路网所示，两列火车都向前驶向纽约站。火车A在轨道2上行驶，而火车B在轨道3上行驶。假设抵达纽约站后，A和B都希望在轨道1上继续行驶。在现实中，可能会发生下列情况。轨道2比轨道3长很多，假设两列火车以同样的速度行驶，火车B会比火车A先抵达纽约站。因此，纽约站的站计算机很可能会授予火车B轨道1的行驶权限。然而，在仿真中，没有模拟行驶所需的时间，因为希望测量的只是决策过程所需的CPU时间，这样就可能会发生下列问题：包含火车A参数的信息比火车B先到达纽约站。也就是说，信息在ARMSTRONG中是异步传播的，火车A的“电子”的速度可能比B快，因此，纽约站的车站计算机可能会先赋予火车A使用轨道1的权限，这就会和实际情况不一致了。但我们要强调的是，这个问题纯粹是由于ARMSTRONG的硬件限制而引起的。

图4.4 分布式仿真中一种潜在的时间问题

为了解决这个时间问题，火车从一个站到下一站所需的时间是通过按比例延迟来模拟的，因而，火车参数实际传播到下一个节点的时间延迟基本上与在ARM-STRONG上的时间延迟相等。