\documentclass[12pt]{article}
\usepackage{CJK}
\topmargin 0in
\headheight 0in
\headsep 0in
\textheight 9.5in
\textwidth 6.3in
\evensidemargin 0in
\oddsidemargin 0in
\parskip 0.16in
\begin{document}
\begin{CJK*}{Bg5}{ming}
\title{心得報告（4/20）}
\author{R94922149 周恩冉}
\date{}
\maketitle

這次課堂上的報告是由我本人負責的，報告的\ paper 是\ {\it Efficient Collective Communication on Heterogeneous Networks of Workstations} 與\ {\it Broadcast Scheduling Optimization for Heterogeneous Cluster Systems}.  主要想解決的問題是如何在\ heterogeneous network of workstations 上有效率地做\ broadcast.

\vskip 0.15in
這裡採用的\ communication model 是\ sender-only 的\ model, 也就是兩個\ processor 傳送訊息的時間由\ sender 唯一決定，且送給每個其他\ processor 是固定的。在同一時間一個\ processor 只能與另一個\ processor 溝通，也就是同一時間只能從另一個\ processor 接受訊息，或是將訊息送給另一個\ processor.

\vskip 0.15in
第一篇\ paper 中提出了兩種\ heuristic, 分別是\ {\it Speed-Partitioned Ordered Chain (SPOC)} 以及\ {\it Fastest-Node First (FNF)} 兩種\ scheduling 方法。SPOC 主要的做法是先建好傳統的\ binomial broadcast tree, 然後將每個\ node 按子樹中的\ node 個數排序，再把傳輸速度最快的\ processor 指定到子樹\ node 個數最多的\ node, 最後按照\ tree 的結構，讓訊息由\ parent 送給\ children.  FNF 則是典型的\ greedy 演算法，每次找到一個可以最早完成任務的\ processor 讓它送給另一個傳輸速度最快的\ processor, 直到所有的\ processor 收到訊息為止。

\vskip 0.15in
第二篇\ paper 主要的工作則是著眼於第一篇所提出的\ FNF scheduling, 證明了\ FNF 是 competitive ratio of 2, 並且說明了\ FNF 在只有兩種速度的\ cluster 與慢的\ processor 傳輸時間總是快的\ processor 的整數倍時所產生出來的解是最佳解，並推論出在\ power 2 cluster 上產生出的也是最佳解。最後提出了一個\ heuristic search, 應用一些本篇中所提出的性質來做\ search 的\ cut, 可以大幅改善\ search 所需要花的時間。

\vskip 0.15in
證明所用的工具主要有幾個，(1) 先證明如果有比較慢的\ processor 排在前面，則一定是排在整數的時間點上，(2) 再證明如果最快的\ processor 排在\ $t - 1$, 慢的排在\ $t$ 則兩個\ processor 一定可以交換位置。有了這兩樣工具後我們就可以推論出一定有一個最佳的\ scheduling 是最快的\ processor 全部排在最前面，由此我們就可以證明在剛剛所提的\ special case 可產生最佳解。

\vskip 0.15in
這裡討論的可說是最基本的\ collective communication --- broadcast, 用的也是最簡單的\ sender-only model, 在這樣簡單的環境中，第一篇\ paper 提出了相當有枯}見的\ FNF 方法，簡單，但威力十足，實在令人激賞。

\end{CJK*}
\end{document}