计算机科学基础

计算的本质是信息处理。在数字计算机上，这种处理是通过二进制逻辑中的符号操作实现的。随着半导体技术的发展，我们通过将更多晶体管集成到计算机芯片中，使计算机的运行速度越来越快——也就是以更高的速度操作位元（bits）。这一现象被称为摩尔定律，始于20世纪70年代。然而，随着物理极限的逐渐显现，这种增长趋势已经放缓，最终将趋于平缓。一些物理学家预测，这将促使新的可能技术取代半导体（硅）作为计算机硬件制造的核心材料。

与此同时，硬件公司通过调整技术来维持硬件能力的增长。例如，多核技术用多个较慢的CPU（称为核心）替代单个快速CPU（中央处理单元，即计算机的大脑），以避免芯片过热。尽管每个核心运行速度较慢，但通过适当安排工作，可以利用多个核心同时完成更多任务。比如，一个强壮的工人每分钟可以搬运100块砖，而一个普通工人只能搬运34块砖。但如果有三个普通工人，他们总搬运量就可以超过一个强壮工人。这就是并行处理的理念。

传统上，计算机程序是用来描述顺序过程的，也就是说，步骤只能一个接一个地按顺序执行。这种程序在单处理器计算机上运行良好，因为计算机一次只能执行一个符号操作。实际上，我们一直在享受摩尔定律的好处：每两年计算机硬件速度加倍，使我们的程序运行速度也翻倍，而我们不需要做任何改变。然而，这一趋势已经停止。单个处理器（核心）的速度没有继续提高，但我们在一台计算机中拥有了更多核心。因此，现有的顺序程序即使在硬件能力增加的情况下，运行速度也可能变慢。在下一代计算机被发明之前，我们可以使用并行计算/处理来更快地解决计算问题。

并行处理的理念并不新鲜。例如，汽车生产流水线允许同时组装多辆汽车。尽管在给定时间内不同部分的汽车正在被组装，这条流水线可以让所有工人保持忙碌，从而提高整个系统的吞吐量（单位时间内生产的汽车数量）。我们可以通过加快工人的工作速度来进一步提高吞吐量，也可以增加另一条流水线并雇佣更多工人。这是一种并行处理形式——流水线作业。另一种并行形式是将整个计算任务分成可以同时计算的部分，并分别在不同的CPU（或计算机）上运行。这类似于和朋友一起拼图。显然，增加帮手可以更快地完成拼图任务，但是否帮手越多越好？答案是否定的。随着帮手数量的增加，协调和沟通的成本增长得更快。当人太多时，他们可能会互相干扰或争夺资源（空间和拼图块）。这被称为并行处理的开销（overhead），导致收益递减。通过测量性能提升与工人数量的关系，我们可以清楚地看到这种模式。

在并行处理/计算中，我们使用一个名为加速比（speedup）的指标来衡量性能的提升。实现的加速比等于没有并行处理时程序的执行时间除以有并行处理时的执行时间：

S=ToldTnewS = \(\frac{T_{\text{old}}}{T_{\text{new}}}\)

其中：

• SS 是加速比；
• \(ToldT_{\text{old}}\) 是没有并行处理时的执行时间；
• \(TnewT_{\text{new}}\) 是有并行处理时的执行时间。

如果并行处理使程序运行速度提高两倍，加速比就是2（即两倍加速）。理论上，随着工人或资源数量的加倍，可以预期加速比也会加倍。然而，实际上很难实现这种理想的加速比，因为某些任务并不总是可以并行化。例如，在地板铺好之前，你通常不能铺地毯；也并非总能通过增加更多画工来更快完成绘画任务。计算任务通常具有类似的依赖关系和资源限制，这会阻碍我们充分利用现有的并行处理系统（如多核计算机）。

练习题：

使用一台洗衣机和一台烘干机，你一次可以处理一批衣物。你先洗衣服，然后将其放入烘干机完成整个任务，假设这需要一小时。如果你只有一批衣物需要处理，没有办法让它更快完成。那么如果有许多批衣物需要处理呢？你至少可以每小时完成一批衣物。能否“加速”这个过程？如果衣物的批数可以任意大，最短的每批衣物平均处理时间是多少？