应用层协议原理 principles of network applications

网络应用体系结构(application architecture):

1. 客户-服务器体系结构(client-server architecture)

server:

• always-on host
• permanent IP address
• data centers for scaling

(并行与分布式计算七)

Arithmetic Computations

线性递推式(linear recurrences)

m阶线性递推式(linear recurrece of order m):
$yi$ 由 $ y{i-1}, y{i-2}, …, y{i-m} $ 的线性组合生成

多项式求值

A = ($ a_0, a_1, …, a_n $)是多项式$ p(x) = a_0x^n + a1x^{n-1 + … + a{n-1}x} + a_n $的系数数组，给定点$x_0$计算$p(x_0)$

• Horner’s algorithm(多项式求值的经典算法: 使用n次乘法和n次加法)
  $$ p(x_0) = (…((a_0x_0 +a_1)x_0 + a_2)x0 + … + a{n-1})x_0 + a_n $$

(并行与分布式计算六)

字符串的预备知识

字符串: 有限长度的字符序列

字符表(或字母表 alphabet)

字符串Y的长度: |Y|

两条字符串X和Y的连接为 XY

字符串Y中第i个字符: Y(i)(1 <= i <= |Y|)

字符串Y的子字符串: Y(i:j)(1 <= i <= j <= |Y|)

字符串Y的前缀(prefix): Y(1:i)(1 <= i <= m)

字符串Y的后缀(suffix): Y(j:m)(1 <= j <= m)

(并行与分布式计算三)

并行搜索的基本思想

在升序数组中采用与二分搜索类似的p+1分搜索:

• 使用递归按比例缩小搜索范围的办法
• 二分搜索每层递归中加入一次比较，p+1分搜索每层递归中加入p次比较
• 上述的每层p次比较可以用p个处理器同时进行

长度为n的升序数组，用p个处理器做p+1分搜索，并行时间为$O(log_{p+1}(n+1))$

(并行与分布式计算五)

computational geometry: design efficient algorithms to handle computational problems dealing with collections of objects in Euclidean space

three technique:

• divide-and-conquer 分治
• plane-sweep tree 平面扫描树
• pipelined divide-and-conquer

凸包(Convex-Hull)计算

(并行与分布式计算四)

连通分量

• 顶点之间的连通性：在无向图G中，若从顶点$v_i$到顶点$v_j$有路径(当然从$v_j$到$v_i$也一定有路径)，则称$v_i$和$v_j$是连通的(Connected)

• 连通图：若V(G)中任意两个不同的顶点$v_i$和$v_j$都连通(即有路径)，则称G为连通图(Connected Graph)

• 连通分量：无向图G的极大连通子图称为G的连通分量(Connected Component)

寻找连通分量的串行算法

(并行与分布式计算二)

列表排序

The list-ranking problem is to determine the distance of each node i from the end of the list

指针跳转法(pointer jumping technique)

思想：

• 链表中的指针跳转可以由一次跳转一步改为一次跳转多步
• 如果能在O（1）时间内一次跳转k步，那么一次跳转2k步只需要双倍时间
• 如果为每个节点，把一次跳转2k步的跳转结果记录下来，那么以后一次跳转2k步也只需要O（1）时间
• 反复利用跳转步数翻倍和跳转结果记录的技巧，可以在O（log N）的时间内把跳转步数扩大为N

因特网

连接到因特网的设备：主机(host)或端系统(end system)

端系统通过通信链路(communication link)和分组交换机(parket switch)连接到一起

路由器(router) 链路层交换机(link-layer switch)

端系统通过因特网服务提供商(Internet Service Provider, ISP)接入因特网

因特网部件运行一系列协议(protocol),协议控制因特网中信息的接受和发送

(并行与分布式计算一)

基础知识

设计分布式并行算法基本流程

1.1发现计算问题的内在并行性

1.2设计与硬件无关的并行算法

迭代器

• 已经定义Array<T>, Pointer<T>和Ptr_to_const<T>使得能部分确保安全性，避免使用指针

• 进一步取代指针，需实现加法、减法和关系运算符

1
2
3
4
5
6
7

void f() {
    int a[10];
    int* pa = a;
    int* end = pa + 10;
    while (pa != end)
        *pa++ = 0;
}

• 基类及派生类都要定义这些操作