Parallel Computing-MIMD

MIMD is the computing pattern, typical in parallel computing systems. Bus is the connection between CPU and memory/other CPU.

clipped from en.wikipedia.org MIMD In computing, MIMD (Multiple Instruction stream, Multiple Data stream) is a technique employed to achieve parallelism. Shared Memory Model Bus-based MIMD machines with shared memory have processors which share a common, central memory. In the simplest form, all processors are attached to a bus which connects them to memory. This setup is called bus-base point where there is too much contention on the bus. Distributed memory It is not economically feasible to connect a large number of processors directly to each other. This type of design can be inefficient because of the added time required to pass a message from one processor to another along the message path. Systems were designed to reduce this time loss and hypercube and mesh are among two of the popular interconnection schemes. Machines using MIMD have a number of processors that function asynchronously and independently. ,

Parallel Computing-SIMD

SIMD refers to the computing technique/paradigm that is usually on a single CPU (i,.e., the SIMD-capable CPU).

clipped from en.wikipedia.org SIMD In computing, SIMD (Single Instruction, Multiple Data) is a technique employed to achieve data level parallelism, as in a vector processor. Advantages An application that may take advantage of SIMD is one where the same value is being added (or subtracted) to a large number of data points, a common operation in many multimedia applications. One example would be changing the brightness of an image. Each pixel of an image consists of three values for the brightness of the red, green and blue portions of the color. To change the brightness, the R G and B values are read from memory, a value is added (or subtracted) from them, and the resulting values are written back out to memory. Disadvantages Not all algorithms can be vectorized. For example, a flow-control-heavy task like code parsing wouldn't benefit from SIMD. Hardware Small-scale (64 or 128 bits) SIMD has become popular on general-purpose CPUs, starting in 1989 [edit] Software SIMD instructions

Spelling Corrector

Input: a word (probably wrongly spelled) A, a set of correct words Bs.
Output: a set of words in Bs that are similar to A (close edit-distance to A).

Algorithms:
result = do 1-radius range query to A.
if(result = null)
result = do 2-radius range query to A.

1-radius query:
for each query, for each each letter in A, remove it or change it with another letter.
So the generated word set S1 are of (25+1)*|A| new words. To see if there is a word in S1 that is identical to a word in Bs. If there is, output this word.

2-radius query:
for each word in S1, repeat previous algorithm.

references:
algo. in java: http://raelcunha.com/spell-correct.php
algo. in python and relevant theory: http://norvig.com/spell-correct.html

Algorithms-C5 Greedy Algorithm

贪心算法的核心是将问题按规模线性增长（1,2,...n）的顺序；其中第i步选择当前最好的选择。核心思想是问题可incremental的解决，即解决了规模为i的问题，则规模i+1的问题只需一些额外的操作，而不需要破坏已有的规模为i的解。贪心算法最好能达到O(n)的复杂度。

此前的图中许多算法，如dijkastra算法即是贪心的思想。

最小生成树：给出有权（无向）图G，其最小生成树MST是连接所有点的一个子图（必为树），且该树的权重和最小。最短路径是站在一个点s的角度看（所有点到s的距离最小），MST是全局的（边权重和最小）。
Kruskal算法：
思想：边排序，选择当前最小权重且与现有生成树R不成环的边。
实现（数据结构）：如何判断边(u,v)与现有生成树R是否成环？--->u和v是否属于R中同一连通分量？--->用Disjoint Set
Prim算法：
思想：当前的选择限制在R周围（与Dijkastra极相似，仅最小的含义不同）
实现：优先队列（键值为点到R的最小边权值，而非到s的最短路径长度）
注意：实现MST过程中有两个要求：保证所选边最小和不成环，但合适的读入顺序只能保证一项。Kruskal是保证的是边最小（边排序），Prim算法保证的是不成环（从现有生成树R相邻的边中选）。而disjoint set能动态（即边update边查询）的支持find-set查询，而优先队列能动态的支持min查询。

Huffman编码
问题：给出一组具有出现频率的元素，如何无前缀编码使得总长度最小？
算法思想：让最rare的元素码字最长，最frequent的元素码字最短（本质是一个线性规划的问题？）
算法实现：每次选择频率最小2个元素合并，更新频率值（频率相加），继续选择。
数据结构：删除最小键值元素，加入->选用优先队列
（Huffman是自底向上的方式执行的）

What can be resolved by Greedy Algo, and what can't?
集合覆盖


PS:
Disjoint Set操作：makeset, find-set, union
实现：Disjoint Set
技术：rank, path compress(why path compress can achieve amortized O(1) time in find-set and union)?

Algorithms-misc

算法思想：
1.分治：大问题分解为不会有重复计算部分的小问题。典型logN复杂度。
2.随机算法（Monte Carlo算法）：以牺牲部分正确性换取速度，如构造 Pr(错误)<1/2。而这种错误的概率能通过常数次迭代消除（运行100次，错误率为(1/2)^100）

Algorithms-C3&4, Graphs

图具有很强的表达能力，在很多实际问题中广泛的应用价值（路由，Web图，非结构数据，等）

图遍历是核心问题，“给出一张图，从其中任一点（源点）开始，如何能不重复的遍历全图。”

一般性算法：
1.图的表示：基本有两种，adjacent table（稀疏图）和adjacent matrix（稠密图）。使用前者，其中顶点vertex是任意排序的。
2.算法：
数据结构：描绘当前的遍历状态有两个<是否访问的boolean数组，队列>（<粉笔，绳子>）
算法：遇到一点（从队列或adjacent table），检查所有邻居，未访问的进队列；当前队列中选择一点出队，访问该点。
复杂度：O(|E|+|V|), 每一顶点访问一次（进队出队）O(|V|), 检查邻居O(|E|),

DFS(Depth First Search)和BFS(Broadth First Search)是以上两种方法的特例——DFS用的数据结构是栈，对先搜到的邻居优先搜邻居的邻居（也可递归实现）；BFS使用队列，对先搜到的邻居先遍历完在找下一层。DFS优势在于能保护图的偏序（或可达性, Va->Vb）关系，能用在有向图强连通问题上；而BFS将全图按到源点的距离组成一棵树，有利于分析路径问题。

有向图强连通问题：
一般性DFS：对于每一点，访问结束标记post值
有向图上的DFS：
任一点可访问（无法连通，则从adjacent table上访问）
无论adjacent order的标记/访问顺序如何， post大的点可达post小的点(但对有有环图，post小的点也可能到post大的点。而DAG中该条不成立,post值实现了拓扑顺序,采用DFS能拓扑排序,post最小是汇点)
有向图连通性：有向图的连通有两重结构，强连通分量（之内任两点有向可达）和DAG（每个分量视为超级点）。
强连通性问题：给出有向图G，如何标记出其所有强连通分量。
two pass算法：
第一遍，reverse G的Gr，用DFS对Gr标记post值。
第二遍，对G按照post的降序访问（Gr的post最大为G的汇点），应用GFS，每一次调用返回一个强连通分量 。

图中的路径：找出所有点到点S的最近路径
无权图的最近路径：BFS，生成到源点S最近路径组成的树(等距离的顶点出现在同一树层中)
有权（权为正）图的最短路径问题：Dijkastra算法:
思想：任一时刻G分为三块R,Rn,和其他。其中R中点的最近路径在R中，Rn是R的邻居集。
Rn中到S最近点点v，其到u的最近路径必为s...->u->v。其中u属于R。
实现：数据结构，需要prev数组记录前一顶点来记录路径。
在前述一般性算法中使用优先队列，并每次检查邻居操作触发一次更新优先队列键值操作。
复杂度为O(|V|*插删队列开销+|E|*更新键值开销)，采用最小堆时O((|E|+|V|)*log|V|)。

有权（有负权）的最短路径问题：有负环时，最短路无意义。
Bellman-ford算法
思想：将所有路径（最长为|V|-1）全部访问一遍（O(|V|*|E|)）
实现：
第i次迭代保证长度为i的最短路径找到；
每次迭代访问所有边（顺序任意），更新该边汇点的路径长度。
讨论：
负环的检测：BF算法多迭代一次（共|V|次），如果有距离减少，则有负环。
DAG的最短路径（不可能有负环）：按照DFS的post降序访问，则能two pass搞定（线性）

PS:
双连通(强连通)性：
针对无向图(有向图)，
同一分量内任意两点至少有两条路径可互达（同一分量内任意两点有向可达），
上层结构为树（DAG），
对边的划分（对点的划分，即连接分量之间的是边）。

DAG的线性化（拓扑排序）：
任一DAG（有向无环图），都能表示为一个线性排列，使得图中的祖先后裔关系能体现为排列的先后关系。
--->Skyline访问顺序?

优先队列：每一数据项绑定一个键值
操作：插入，删除（只删最小键值的项），更新键值
实现：数组，二分堆，Fibonacci堆。。。（根据操作种类的次数选择实现）

Algorithms-C2 Divid-and-conquer Algorithms

分治算法思想是将一个问题分拆为多个子问题，解决子问题（在递归最底层解决），并合并结果。分治算法的复杂度有三个因素影响，a、b、d；分拆成a个子问题，每个子问题规模为1/b，合并或分拆的开销为O(n^d)：判断d~log_b^a大小，前者大的时候，d是决定性因素；相等，则复杂度为nlogn；小于，则ab是决定性因素。

经典的分支算法是合并排序：将一个长度为n的数组排序，将其分拆为两个等长的子数组排好序之后合并。两个子问题没有重叠，即“a=b。”又合并复杂度为O(n)。故总复杂度为O(nlogn)。树上有证明这是最优的bound。

另一问题是寻找中项（或者第k项）：寻找一个乱序数组的第k大的项。与merge排序的区别在于中项寻找算法先对无序数组有序划分，然后递归再合并的时候就方便了。而merger算法是做无序划分，合并的时候复杂度为O(n)。

快速排序是两者的结合；排序算法但进行有序划分。
快排VS归并排序
优势：无额外空间（适合大文件排序），移动次数少（适合小数据类型，如整数数组排序）
劣势：比较次数多（不适合Object排序，其比较操作耗时）
快排实现：在递归的底层（如长度只为10的小数组），不要用快排，直接用冒泡（生成随机数费时）

乘法的计算：大整数的乘法，矩阵乘法和多项式乘法。整数前n/2位和后n/2位，矩阵则为四个象限。多项式的乘法介绍如下：

多项式乘法（或者说矢量之间卷积）在信号与系统中有应用（如对时不变线性系统，第d+1时刻的信号（多项式函数）值是前d个时刻该多项式值与对应脉冲多项式的乘积；也可以计算大整数乘法）FFT傅立叶变换是解决这个问题的方法。具体如下：
多项式本身有系数表示和值表示两种，用值表示的时候乘法可以O(n)下完成。计算思路是把系数表示转换为值表示，做乘法，再转回来。核心问题是如何做转换，描述如下：
“多项式f(x)=a_(n-1)*x^(n-1)+...a_1*x+a_0求x=x_0,x_1,...x_(n-1)值。” 本质上这是一个矢量和矩阵乘法的问题（[f(x)]=M(x)*[a_0,...a_(n-1)], M矩阵见书），技巧之处在于如何选择n个x值，使得计算能够简化。思路如下：
使用1的n次方根w作为x，使得系统能够递归调用。详细见书！（矩阵能分拆成四个小矩阵，其中两个是重复的。）

Algorithms-C1 Algorithms with numbers

两个主题：数字算法和素数相关理论

数字算法应用于硬件上的实现。基本的算法关注复杂度，加减法O（n），乘法采用2X*Y/2进行递归复杂度为O(n2)。

真正实现时候考虑考虑补码，即模运算下的加减乘除。补码涵盖了大多数的数字范围，而模运算的思想暗示了对于大数计算的扩展性。补码X和原码X'是不同定义域的等价类。（由于X=X'mod256,故X+Y=(X'+Y')mod256.其中256保证不需要进位。）特别的是模运算下的除法，对于modN，只有当a与N互素，模除a（也就是乘以a*exp(-1)）才有意义，否则找不到数字b, s.t. a*b=1modN。

素性测试, To Be Continued...

？模除的实际意义？

Cloud Computing and System Rresearch--Haibo Chen's doctoral Defense

Five separate issues in cloud computing are addressed by the Haibo, that is, Security, Maintainability, Availability, Reliability and Trustworthy, interestingly abbreviated just as SMART.

Different from Cluster Computing and Grid Computing, Cloud Computing is used in the scenario where an enterprise outsources its computing/storage power and provide related services to users (including individuals and small enterprises). The Cloud is typically a computer farm, in which a host of computers are typically organized as two-level structure, the hardware and VMM (OS is built over VMM).

Maintainability means the degree of ease by which administrator can manage the whole system. For instance, how to update software "lively," that is, without stop-and-restart the system. The crux is how to do so in a multi-threaded setting or at a OS level, in both of
which cases a update point can't be easily located (update-point means a code snippet which isn't referenced by any running object)... The solution seems involving adding a JMP instruction into the assembler...

Reliability, or to say fault-tolerance, is to treat failover of hardware. Since VMM is built over hardware, virtualization and migration are two typical way to guarantee software and data availability while hardware undergoes failover. For details, refer to Haibo's ICPP07 best paper, Mercury.

Security is a big problem in system research. DIFT is common solution, in which suspicious code (as assembler) is marked as tainted at the beginning, and tracked later. The problem is that current hardware can't support tracking efficiently (overhead up to 3.6X in a Micro'06 paper by Yuanyuan Zhou). An alternative is to add new hardware, which apparently is not practical at present. The SHIFT proposed by Haibo achieves 1.2X overhead by simulating tracking using Control Speculative in current hardware....


Future work:
multi-core system, and MapReduce (suitable for parallel computing but not for scientific computing).

Further questions:
What on earth is VMM? and 代码段 (a mapping from assembler to machine code?)

References:
http://ppi.fudan.edu.cn/system/people/~hbchen.htm

Graph in database and data with semantics

There are general two meanings when mentioning graph in database community.

In the first category, the data is graph. That is, the graph database deals with how to store the data that is conceptually organized as a graph. Specific queries like subgraph isomorphism is required, and such database can find its use in some scientific computing/applications(?).

In the second category, graph is intended to integrate heterogeneous data; Graph is a general symbolic that can represent structured, semi-structured, and unstructured data in a unified way. For structured data, each tuple is treated as a vertex (actually, a small graph with each attribute being a vertex) in a graph that is connected by foreign keys (or tuple join). For unstructured data, say webpages, each page is a vertex and each link is an edge.

Let's talk a bit more on the second category. To synthesize structured and unstructured data (or merging IR and DB community) is quite a meaningful task. On one hand, conventional database lacks data access method like keyword-based queries, which are quite common in IR. Such queries can provide users richer search facility[1]. On the other hand, today's IR systems only support pure keyword search, that is, they treats all keyword as dead query entries, unaware of any semantics behind them. The keyword search is unable when one want results with semantics like "find all professors' phone numbers in CS dept., Wisc."[2]

[1] Guoliang Li, et al " EASE: Efficient and Adaptive Keyword Search on Unstructured, Semi-structured and Structured Data."
[2] Entity search. http://wisdm.cs.uiuc.edu/

Script language

不同于系统语言，脚本语言有如下些特点：
1.嵌入到已有的系统，提高系统功能可扩展性，支持快速开发

2.解释执行：没有编译（执行的时候编译），可一行一行的执行（can run in a command-line manner）

例如BeanShell是一种运行在JVM上，遵循Java语法的脚本语言。“BeanShell是一种受欢迎的testing 和debugging工具。”

to be continued (refer to my clip).

overlay (concept)

recent investigation on overlay while looking for profs' interests

clipped from en.wikipedia.org Overlay network overlay network connected by virtual or logical links, each of which corresponds to a path, perhaps through many physical links, in the underlying network. The overlay has no control over how packets are routed in the underlying network between two overlay nodes, but it can control, for example, the sequence of overlay nodes a message traverses before reaching its destination. an overlay network can be incrementally deployed on end-hosts running the overlay protocol software, without cooperation from ISPs D. Andersen, H. Balakrishnan, M. Kaashoek, and R. Morris. Resilient Overlay Networks. In Proc. ACM SOSP, Oct. 2001. J. Jannotti, D. K. Gifford, K. L. Johnson, M. F. Kaashoek, and J. O'Toole. Overcast: reliable multicasting with an overlay network. In Proc. USENIX OSDI, Oct. 2000. L. Subramanian, I. Stoica, H. Balakrishnan, and R. H. Katz. OverQoS: An overlay based architecture for enhancing Internet QoS. In Proc. NSDI, 2004.

Debut

Give a test here. Seems the blogger is much more accessible than MS live space. Root for google!