多线程算法

相对我来说比较局限,因为 js 是单线程的,所以只做了解,后续如果要用到可以在进行进一步的掌握。 首先来讲,目前的大部分算法都是基于单线程,或者说串行的模型来构建的。

概念

想要理解多线程编程模式,就必须从多线程的基本概念上入手

首先,目前的大部分计算机都利用了共享存储的概念,也就是每个核心都能访问全部的内存。 静态线程, 静态线程提供了一个虚拟处理器软件的抽象,即 线程,你可以认为线程就是计算机的一个虚拟核心,并且他能够访问全部的内存,与其他线程共享内存。称之为静态是因为该线程一般不会去创建销毁,因为其时间成本相对较高。系统将会加载线程到处理器上执行,并在其他线程需要处理时交换出来。 由于直接进行静态线程层面上的编程难度较高。所以一般都是基于某些 并发平台 进行编程。

fib

下面 我们通过一个多线程的 fib 计算伪代码来对多线程算法进行理解

p-fib(n)
  if n <= 1  return n
  x = spawn p-fib(n - 1)
  y = p-fib(n - 2)
  sync
  return x + y

其实,相比较普通的 fib 而言,真正的不同就两个点,spawn 和 sync

spawn 代表开启一个派生子进程,这个进程将会和父进程同时运行 sync 等待上面所有派生的子进程都运行完毕后再执行接下来的代码

所以我们代码其实会产生非常大量的子进程,也会有很大量的重复计算。

性能

多线程的算法性能衡量标准有两个 工作量(work)持续时间(span) ,工作量代表是所有的工作在处理器上运行的总时间,持续时间代表了一条从顶点到底部最远的路径(把多线程算法运行看成是树)的长度。可以认为是程序运行的实际时间。可以认为工作量,那么系统负载会很高。如果持续时间长,那么程序会很慢。

同时 我们把 TP 代表一个程序在有 p 个处理器情况下的运行时间,用 T1 代表这个程序在有 1 个核心下的运行时间

接下来,给出一些重要定律

工作量定律 TP >= T1 / P 这个定律直接揭示了多线程运行某个算法的下界,一个最佳并行算法也无法让他的速度做到快于 单核情况下的工作时间/P 。因为在理想情况下,一个最佳并行程序最大同时只能运行 P 步。

持续时间定律 TP >= T∞ 一个程序在 P 个核心上不可能比在无限核心的计算机上运行的更快。

加速比(T1 / TP),代表该算法在 p 个核心的计算机上运行比在 1 个核心的计算机上运行快了多少倍,如果 加速比等于 p,那么就代表已经达到了完美加速比。有几个核心就快几倍 猛爆了。

并行度(工作量/持续时间)代表一个算法的最大可能的加速比,比如一台计算机为 10 核心,但是某个算法的并行度只有 2,那么这个计算机的另外 8 个核心几乎无法利用。你可以认为把算法看成一棵树,他的并行度越高,越会往横向去展开。他就像是某个算法的极限。并且越是超级计算机,提高程序的并行度就非常重要。高的并行度可以让程序更有生命力,更具扩展性。

调度器的性能也会影响我们对计算速度,一个好的调度器能够将我们的任务,也就是子进程去平衡的分配到计算器的线程中,当然一个调度器基本上不能做到完美的调度,也就是极限的去利用多线程。似乎设计到 NP 完全问题。

同时,一个多线程算法也要注意竞争问题,即两个并行指令对同一块内存进行操作,出现丢失问题,这个本身具有随机和不确定性,所以要避免这些情况,并行指令或者进程之间应该尽可能的独立,避免干扰操作。