---
# System prepended metadata

title: homework 6 report
tags: [1101_平行程式設計, 報告, parallel, report]

---

# homework 6 report
姓名: `張議隆` 學號: `F74082125`
程式碼放置於`~/hw6`底下的`h6_problem1.c`

整體來說...這次作業應該算是失敗的
我把整個程式架構設計完後，完全看不到程式可以正常結束
這隻程式是可以跑的，但是執行時間過久
久到我也不知道結果是否正確
以下我放上程式的流程圖
## Flow Chart
```flow
st=>start: start
get_matrix=>operation: Read Matrix
initialize=>operation: Initialization
start=>operation: start of parallelization(open MPI)
ant_s=>operation: start of ant algorithm
place_ant=>operation: randomly place ants(place cities * 2 / 3 ants)
local_init=>operation: initialize private variables
start_a=>operation: start of parallelization(omp)
choose_city=>operation: choose city based on where ants are
route_check=>condition: has all ants got the route to visit all cities?
get_cost=>operation: calculate how much cost this route is
update_cost=>operation: update local cost to global cost
update_pheromone=>operation: update pheromone matrix
loop_check=>condition: has run nc(100) times?
end_a=>operation: end of parallelization(omp)
clear_local=>operation: free memory spaces of local variables
end=>operation: end of parallelization(open MPI)
output=>operation: print the best route and cost
clear_global=>operation: free memory spaces of global variables
e=>end: End

st->get_matrix->initialize->start->start
start->ant_s->place_ant->local_init->start_a->choose_city
choose_city->route_check
get_cost->update_cost->update_pheromone->loop_check
clear_local->end_a->end->output->clear_global->e
loop_check(yes)->clear_local
loop_check(no)->start_a

route_check(no)->choose_city
route_check(yes)->get_cost
```

## 困難點
整隻程式基本上都死在`choose_city()`這個function內
這個function耗太多時間在隨機選取要前往的城市
當然也有可能是我的參數設置有錯誤
這部分因為我真的測試不出來，我也沒有辦法進行微調

測試執行時使用4個thread，2個process執行
我從開始打這份文件到打完快一小時了
第一次 ant algorithm 的迴圈都沒跑完
## 參數設置
`init_pheromone()`: rand_max = 251(把pheromone matrix做隨機分配的質數)
`choose_city()`: alpha = 0.6, beta = 0.4
`update_pheromone()`: evaporation rate = 0.4, Q = 3

程式執行方式如下:
```
mpirun -n <process count> ./sim <thread count> <city cost file> <city count>
e.g.: mpirun -n 2 ./sim 4 gr17_d.txt 17
process count: 使用多少個process執行
thread count: 使用多少個thread執行
city cost file: 存有city cost matrix的檔案名稱
city count: 上面那份文件內總共有幾個city
```
###### tags: `1101_平行程式設計` `報告` `report` `parallel`