并行计算中的环形算法与灵活环设计

# 并行计算中的环形算法与灵活环设计 ## 1. 简单令牌环协议 在令牌环网络中，信息的传递遵循一定的规则。当一个信息被发送到环上时，IMP（Interface Message Processor）会根据信息的目的地ID进行不同的处理： 1. **信息未到达目的地**：如果信息的目的地ID与IMP的ID不匹配，IMP会将信息原样写入环中，并清除已接收信息的标志。同时，IMP会向环中写入一个TOKEN消息。 2. **信息到达目的地**：如果信息的目的地ID与IMP的ID匹配，说明该信息是发给IMP或其连接的主机的。IMP会向标准错误输出打印一条状态消息，报告消息的类型。然后，IMP会将消息的状态改为ACK，并将消息写回环中。如果消息是发给主机的，IMP还会通过管道将消息发送给主机。 3. **实际协议的复杂性**：实际的IEEE 802.5令牌环协议要复杂得多。IMP使用一个令牌保持定时器，在传输开始时设置为预设值。IMP可以一直传输，直到定时器到期，因此消息可以很长。此外，还可能存在优先级方案。在实际的令牌环协议中，有一个IMP被指定为环的活动监视器，它会定期发出控制帧，告知其他站点活动监视器的存在。活动监视器还负责检测令牌是否丢失，并重新生成令牌。所有站点会定期向下游发送备用监视器存在控制帧，以检测环是否中断。 ### 1.1 程序修改与主机生成程序 我们需要对原程序进行修改，使其在创建环后，每个IMP进程创建两个管道和一个子主机进程。子主机进程的标准输出和标准输入需要进行重定向，使其执行hostgen程序，并传递相应的命令行参数。IMP会进入一个无限循环，使用select函数监控可能的输入。当有输入可用时，IMP会执行上述简单的令牌环协议。 hostgen程序是一个独立的程序，它接受两个命令行参数：一个整数进程号n和一个整数睡眠时间s。该程序会监控标准输入，并将接收到的任何输入记录到标准错误输出。它使用一个随机超时时间（0到s秒之间）来读取输入。如果发生超时，它会向标准输出写入一个0到n之间的随机整数。我们需要单独测试hostgen程序。 ### 1.2 流程图 ```mermaid graph TD; A[信息发送到环上] --> B{目的地ID与IMP ID匹配?}; B -- 否 --> C[IMP原样写入信息到环中，写入TOKEN消息，清除标志]; B -- 是 --> D[IMP打印状态消息，改状态为ACK，写回环中]; D --> E{消息是发给主机的?}; E -- 是 --> F[通过管道发送消息给主机]; E -- 否 --> G[结束处理]; C --> G; ``` ## 2. 流水线预处理器 ### 2.1 C预处理器的工作原理 C预处理器（cpp）用于预处理C源代码，使得C编译器不必处理某些特定的任务。例如，当C程序中有`#define BUFSIZE 250`这样的语句时，cpp会将所有出现的`BUFSIZE`替换为250。但它不会将`BUFSIZE1`替换为`2501`，因为它处理的是令牌（token）。不同版本的cpp处理递归可能产生的循环问题的方式不同。一种方法是不对已经替换过的字符串进行额外测试，但这种方法在处理一些简单语句时会失败，例如： ```c #define BUFSIZE 250 #define BIGGERBUFSIZE (BUFSIZE + 1) ``` 另一种方法是对输入文件进行多次遍历，每次处理一个`#define`语句，并按顺序进行替换。使用流水线可以更高效地（甚至并行地）完成处理。 ### 2.2 流水线的实现 我们要基于原程序实现一个流水线预处理器。为了简化编程，预处理器只将单个字符转换为字符串。具体步骤如下： 1. **编写processchar函数**：该函数的原型为`int processchar(int fdin, int fdout, char inchar, char *outstr);`。它会从文件描述符fdin读取数据，直到文件结束，并将任何出现的字符inchar转换为字符串outstr，然后写入文件描述符fdout。如果成功，函数返回0；如果失败，返回 -1 并设置errno。在将该函数用于环之前，需要编写一个驱动程序进行测试。 2. **修改原程序**：将原程序修改为接受四个命令行参数（ringpp），运行命令为`ringpp n conf.in file.in file.out`。其中，n指定流水线的阶段数，对应原程序中的nprocs - 2。原始父进程负责通过读取file.in文件生成流水线的输入，最后一个子进程负责从流水线中取出输出并写入file.out文件。在创建环之前，原始父进程会打开conf.in文件，读取n行，每行包含一个字符和一个字符串，并将这些信息存储在一个数组中。 3. **原始父进程的工作**：原始父进程将file.in文件的内容复制到其标准输出。当遇到文件结束符时，进程退出。它只负责生成流水线的输入，不进行任何流水线处理。 4. **最后一个子进程的工作**：最后一个子进程将其标准输入的数据复制到file.out文件，但不进行任何流水线处理。当遇到标准输入的文件结束符时，进程退出。 5. **中间子进程的工作**：对于编号在2到n + 1之间的子进程，它会使用翻译数组中第(i - 1)项的信息将一个字符转换为一个字符串。每个子进程就像一个过滤器，从标准输入读取数据，进行替换，并将结果写入标准输出。它会调用processchar函数来处理输入。当processchar函数遇到输入的文件结束符时，每个进程会关闭其标准输入和标准输出，然后退出。 6. **测试与优化**：在确保程序正常工作后，我们可以使用一个大文件（数兆字节）和适量的进程（10到20个）进行测试。如果可能的话，还可以在多处理器机器上运行该程序，以测量加速比。 ### 2.3 表格：各进程的职责 | 进程类型 | 职责 | | ---- | ---- | | 原始父进程 | 读取file.in文件，生成流水线输入，不进行处理 | | 中间子进程 | 使用翻译数组进行字符替换，调用processchar函数 | | 最后一个子进程 | 从流水线取出输出，写入file.out文件，不进行处理 | ### 2.4 流程图 ```mermaid graph TD; A[原始父进程读取file.in] --> B[写入标准输出]; B --> C[中间子进程1读取标准输入]; C --> D[中间子进程1进行字符替换]; D --> E[中间子进程1写入标准输出]; E --> F[中间子进程2读取标准输入]; F --> G[中间子进程2进行字符替换]; G --> H[中间子进程2写入标准输出]; H --> I[最后一个子进程读取标准输入]; I --> J[最后一个子进程写入file.out]; ``` ## 3. 并行环形算法 ### 3.1 并行处理与加速比 并行处理是将一个问题分解为多个部分，使得这些部分可以并行解决，从而减少整体执行时间。衡量并行处理效果的一个指标是加速比S(n)，其定义为： \[S(n) = \frac{\text{单处理器执行时间}}{\text{n处理器执行时间}}\] 理想情况下，执行时间与处理器数量成反比，即加速比S(n)等于n。但在实际应用中，由于存在一些无法并行处理的工作，以及处理器同步和通信的开销，线性加速比很难实现。 ### 3.2 图像滤波算法 #### 3.2.1 滤波器的类型 滤波器是对图像进行变换的操作。根据变换类型的不同，滤波可以去除噪声、增强细节或模糊图像特征。这里我们考虑一个由n×n字节数组表示的灰度数字图像。常见的空间滤波器会根据原始像素及其邻域的函数来替换每个像素值。滤波器算法使用一个掩码来指定参与计算的邻域。例如，一个3×3的最近邻掩码可以表示一个线性滤波器，它是掩码内像素的加权和。而非线性滤波器则不能表示为掩码下像素的线性组合，例如取邻域像素的中位数就是一个非线性滤波器。 #### 3.2.2 具体的滤波操作 假设一个由n个进程组成的环要对一个n×n的图像进行滤波。每个进程可以负责计算图像的一行或一列的滤波结果。由于ISO C按行优先格式存储数组，让每个进程处理一行更为方便。在进程p中进行滤波操作的步骤如下： 1. **获取原始图像的行*