:::danger
老師重新說明一次 CAN 要考慮自己，然後什麼不可以拿自己證
:::

# Intro

這週的 System design 只是其中很小的一部分，但老師希望我們可以透過這次的內容瞭解到 System design 是要符合很多 constrain 跟 最佳化的問題。
>老師：車廠從開始設計到開始製造可能會花 1 到 2 年的時間

第 3 頁右邊的圖是個垂直來看 Layered design 的圖，其中的每個 layer 都可以是一個 system design 的問題；這堂課要著重的是如何把 software 那層 map 到下面 Hardware 那層，當中的 System design 問題。

:::info
從那張圖可以發現，首先透過抽象化技巧把想做的事情拆成很多層，然後就可以著手對各層做 System design
:::

## 早期的問題

System Design 會決定哪些 task 要分配到哪些 ECU，以及哪些 signal 要由哪些 message 來傳輸，同時決定了那些硬體器材的規格要開到多少。

因為那些硬體器材通常是由其他家廠商做的，但是他們製作總需要時間，所以 System Design 算是很早期就要先弄好的一件工程，才可以告訴製造廠我們需要的規格。

## Model-Based Design

有三件事情：`Model`、`Design`、`Analysis`

Model-Based Design 是在自己定義的 `Model` 上面「做 `Design` 跟 `Analysis`」。

但是這三件事情沒有所謂的先後順序，而是互相影響彼此，例如：

- 通常在 `Design` 的時候同時也會受 `Analysis` 的結果影響，就像上週提到 TDMA-Based protocol 在 Asynchronous 情況下要越平均越好
- `Model` 的好壞也會影響 `Design` 的難易度

其實還有第四件事情：`Implement`，就是把我們的 `Model` 跟 `Design` 真的 `Implement` 出來。

---

# Mixed Integer Linear Programming / MILP

:::warning
非常基本的用數學解最佳化問題的方法，老師說雖然跟車子毫無關聯，但是這可以讓我們在各方面很受用。
>感謝老師，讚嘆老師
:::

## Linear Programming

在講 MILP 之前，一定要先提到 LP。

他就是國中(還是高中?)有提到的線性規劃問題，但是那時候都只有提到 2 維的。

總之以 2 維來說，問題就大概長得像：

$$
\begin{align}
\text{Maximize：}&2x-y\\
\text{Subject to：}& x-y\le1\\
2y\le3\\
x,y\ge0\\
x,y\in \mathbb{R}
\end{align}
$$

通常 Subject 的內容可以圍成一個多邊形，然後你要做的就是把想要 Maximize(或 Minimize) 的斜直線到處平移找到最大(最小值)。

如果是多維的話就會變成超平面到處平移找到超維體的某個地方，得到極值。

而解 LP 問題時，現在會使用的方法就是先轉成 Canonical form：

$$
\begin{align}
\text{min：}&\mathbf{c}^{T}\mathbf{x}\\
\text{subject to：}&\mathbf{Ax}\le\mathbf{b}, \mathbf{x}\ge 0, x\in \mathbb{R}\\
\end{align}
$$

然後再搭配一些演算法，例如 Simplex algorithm 來解。
>不同的軟體用的演算法，以及 Canonical form 可能都會不同，請參閱公開說明書

## Integer (Linear) Programming ILP

$$
\begin{align}
\text{Maximize：}&2x-y\\
\text{Subject to：}& x-y\le1\\
2y\le3\\
x,y\ge0\\
x,y\in \mathbb{Z}
\end{align}
$$

簡單來說就是 LP 問題，但是每個維度的值只能是整數。

很可惜的是這是個 NP-Complete 問題，目前尚未有線性時間的演算法可以找到最佳解，大多都是找到某個解但不一定是最佳解。
>如果你找到的話，你就可以證明 P=NP 了 ：)

## Mixed Integer Linear Programming ILP

$$
\begin{align}
\text{Maximize：}&2x-y\\
\text{Subject to：}& x-y\le1\\
2y\le3\\
x,y\ge0\\
x\in \mathbb{R}\\
y\in \mathbb{Z}\\
\end{align}
$$

Mixed 的意思就是混合了整數跟實數，如上面的例子，就是 x 軸是實數，但是 y 軸只能是整數；MILP 雖然一樣是 NP-Complete，但是因為有些軸是實數，所以有一些較好的算法可以求得不錯的解。

:::info
總之 LP、ILP、MILP 只要照著使用說明書轉成該軟體所要的 Canonical Form，就可以得到你想要的解(近似解)了。
>但是不確定會跑多久，通常面對大型問題會很慢
>例如我的「機器學習安全特論筆記」有提到的 Certified Robustness 就有用到 MILP 做驗證，但是很慢：)
:::

## Quadratic Programming / QP

既然講到了 LP，那當然就要提一下 QP。

Canonical form 如下

$$
\begin{align}
\text{min：}&\frac{1}{2}\mathbf{x}^{T}\mathbf{Q}\mathbf{x}+\mathbf{c}^{T}\mathbf{x}\\
\text{subject to：}&\mathbf{Ax}\le\mathbf{b}, \mathbf{x}\ge 0, x\in \mathbb{R}\\
\end{align}
$$

一樣是詳閱公開說明書，就有熱騰騰的現成工具可以用。
>可以順便參考我的「林軒田老師 機器學習技法筆記」當中支持向量機的部分

## Convex optimization

這是 QP 的更 general 的形式。

$$
\begin{align}
\text{max：}&f(\mathbf{x})\\
\text{subject to：}&g_{i}(\mathbf{x}),\ \forall i\\
\end{align}
$$

其中 $f$ 跟 $g_{i}$ 是 convex 的。

:::warning
By wiki：
[**凸函數**](https://zh.wikipedia.org/zh-tw/%E5%87%B8%E5%87%BD%E6%95%B0)（英文：Convex function）是指[函數圖形](https://zh.wikipedia.org/wiki/%E5%87%BD%E6%95%B0%E5%9B%BE%E5%BD%A2 "函數圖形")上，任意兩點連成的線段，皆位於圖形的上方的[實值函數](https://zh.wikipedia.org/wiki/%E5%AE%9E%E5%87%BD%E6%95%B0 "實函數")
:::

---

# Simulated Annealing 模擬退火

有時候在找最小值的時候，找到的其實是 local optimal，不是 global optimal，這時候就要犧牲一點往高的地方走，擺脫 local optimal 後再次開始搜尋。

>老師的人生哲學：這期時就跟人生很像，有時候遭遇到了困難讓情況變得更糟令你很挫折，
>但是這或許就是一個讓你改變的機會，擺脫 local optimal，達到 global optimal

## 背景概念

跟鐵匠在鍛造的時候很像，「溫度高的時候」比較可以做「較大的改動」，「溫度低的時候」比較會去做「較小的改動」。

## 數學式子

溫度在這裡也可以叫做「時間」。從腳下的點 $S$，想要走到令一個點 $S^{\prime}$，會根據「兩點的高度差距」以及「總共經過的搜尋時間」決定一個機率，以該機率判斷要不要跳過去。

$$
\begin{align}
&Prob[S\rightarrow S^{\prime}]=\min(1,e^{\frac{-\triangle C}{T}})\\
&\triangle C= \text{cost}(S^{\prime})-\text{cost}(S)
\end{align}
$$

min 其實可以看作是：

- 如果 $\triangle C \le 0$
- 也就是 $S^{\prime}$ 的 cost 更低，那麼就一定給他走過去
- 如果 $\triangle C > 0$
- 此時雖然 cost 變高，但是有一定的機率會走過去

## Algorithm

- 得到初始 $S$
- 得到初始溫度 $T>0$
- $S^{*}$ 是解，先令 $S^{*}=S$

while 還沒冷卻
    在 S 附近隨機挑出一個鄰居 S'
    算出 Cost
    如果 Cost 比較低就直接跳到 S'，並令 S*=S
    否則算出機率，再用機率決定要不要跳過去，決定要不要令 S*=S
    T = rT, 其中 0 < r < 1
回傳 S*

## 注意事項

- 解空間
- 如何找鄰居
- 例如通常會在當前的 $S$ 附近開始搜索
- 如何評估 Cost
- 老師有強調 Invisible Solution 的重要性
- 所謂不可見解，就是搜索過程中沒有拜訪到的點
- 雖然沒有拜訪到，但是他們會對你如何訪問下一個點產生影響
- 如何降低溫度

:::warning
雖然 Simulated Annealing 不一定是最佳解，但是通常相比 MILP 會比較快
:::

:::info
詳細的部分我會補充在「人工智慧導論」的筆記
:::

---

# CAN Mapping Problem

學完上面的技巧，搭配之前的 Timing Analysis，現在終於可以來最佳化 Mapping Problem 了。

以下會針對四個項目各自做最佳化：

- Task Allocation
- 哪些 Task 要給哪些 ECU
- Signal Packing
- 哪些 Signal 要給哪些 message
- Task Priority Assignment
- Message Priority Assignment

## Task Allocation

- Indices 跟 Variable
- task 的 index 有 $i$ 跟 $j$
- ECU 的 index 有 $k$
- $a_{i,k}$：[0,1]，代表 task $i$ 有無放在 ECU $k$ 上面
- $s_{i,j}$：[0,1]，代表 task $i$ 跟 task $j$ 有無放在同個 ECU 上面
- Contraints
- $\forall i\ \sum_{k}a_{i,k}=1$ 也就是 1 個 task 就只有 1 個
- $\forall i, j, k,\ a_{i,k}+a_{j,k}+s_{i,j}\ne 2$
- 此時要注意 $s_{i,j}$ 只是代表有沒有放在同個 ECU 上面
- 如果兩個 $a$ 都是 1，那麼 $s$ 一定是 1，加起來就是 3
- 如果兩個 $a$ 一個 1 一個 0，那麼 $s$ 一定是 0，加起來就是 1
- 如果兩個 $a$ 都是 0，那麼 $s$ 可能是 0 或 1
- 總之絕對不等於 2

:::info
$s_{i,j}$ 在後面才會用到。
這裡我們並沒有對 ECU 可以放多少 task 有限制，但是之後的 Timing Analysis 就會對他做出制裁。
:::

## Task Priority Assignment

- Indices 跟 Variable
- task 的 index 有 $i$、$j$ 跟 $j'$
- $p_{i,j}$：[0,1]，代表 task $i$ 比 task $j$ 有無更高的 priority。
- Contraints
- $\forall i,j, i\ne j\ \ \ p_{i,j} + p_{j,i}=1$
- 1 個 task 一定有更高的 priority
- $\forall i,j,j', i\ne j,i\ne j',j\ne j'\ \ \ p_{i,j} + p_{j,j'}-1\le p_{i,j'}$
- 如果大小關係是 $i>j>j'$，那麼上面就會是 $1+1-1\le 1$
- 如果是其他的大小關係，左手邊要嘛是 0 或 -1，右手邊要嘛是 0 或 1

:::warning
那為何 indices 不是設置像 $p_i：[1,...,n],\text{for i in 1 to n}$？
因為這樣的話， constraints 會變成需要 $p_i\ne p_j$，但是這樣的 constraints 會需要做轉換。
也就是 $p_i>p_j$ 或 $p_j>p_i$
但如果想要把這兩條 `OR` 轉成 MILP 需要的 `AND`，還是會需要用到上面提到的 $p_{i,j}$：
$$
p_{i,j} + p_{j,i}=1\text{ and }(p_i-p_j)<(1-p_{i,j})M\text{ and }(p_j-p_i)<p_{i,j}M
$$
其中 $M$ 是一個很大的 constant。
那這樣還不如直接用上面的方法；而且 $M$ 可能會導致 MILP 運算變很慢
:::

## Signal Packing

>老師說是這章節最困難的一張投影片

- Indices 跟 Variable
- $i$ 跟 $j$ 是 task 的 index；$k$ 是 ECU 的 index；$l$ 是 message 的 index；
- $T_{i,j}$ 是 task $i$ 到 task $j$ 的 signal 的 period
- $T_{k,l}$ 是 ECU $k$ 的 message $l$ period
- $a_{i,k}$：[0,1]，代表 task $i$ 有無放在 ECU $k$ 上面
- $t_{i,j,k,l}$：[0,1]，代表 task $i$ 往 task $j$ 的 signal 有無放在 ECU $k$ 的 message $l$ 上面
- $v_{k,l}$：[0,1]，代表 ECU $k$ 的 message $l$ 有無被使用
- Contraints
- $\forall i,j,k\ \sum_{l}t_{i,j,k,l}=a_{i,k}(1-a_{j,k})$
- 如果 task $i$ 跟 $j$ 都放在 ECU $k$ 上面，那他們之間不用有 signal，所以加起來是 0
- 如果沒有放在同個 ECU 之間，但是 signal 有方向性，$t_{i,j,k,l}$ 是 $i$ 往 $j$ ，因此只有當 $i$ 有放在 $k$ 上面的時候，加起來才會是 1，否則就是 0
- $\forall i,j,k,l\ \ \ t_{i,j,k,l}\le v_{k,l}$
- 也就是 ECU $k$ 的 message $l$ 要嘛有用要嘛沒有用
- $\forall i,j,k,l\ \ \ t_{i,j,k,l}\times T_{k,l} \le T_{i,j}；t_{i,j,k,l}\times T_{i,j} \le T_{k,l}$
- 這其實是把 $t_{i,j,k,l}\times T_{k,l} = T_{i,j}$ 拆開來
- 也就是如果要把 $i$ 傳到 $j$，想透過 $k$ 的 $l$，那麼兩者的 period 一定要一樣

:::info
可以回顧到上面 task allocation 並沒有限制一個 ECU 上可以放多少 task
:::

:::warning
為什麼需要 Packing？
因為大多汽車內的訊號都是 1 個或 2 個 bit，如果每次傳輸都只傳少少的資料，CAN 原本的 data efficiency 已經夠差了，這樣會更差，因此把多個要傳的訊號打包在一起一次傳出去，會更有效率。
當然接收者要知道自己想要的資料是位於 data field 的哪個區段。
:::

## Message Priority Assignment

跟 Task Priority Assignment 是一樣的，頂多名稱換一下。

## Timing Constraints

有了上面四大種 variables，以及一些附帶的 constrains 之外，還需要一些跟時間有關的 constraints

- Task
- 就是 ECU 內部 preemptive 形式算出的 Response Time
- $R_i=C_i+\sum_{p_i<p_j}\left\lceil\frac{R_i}{T_i}\right\rceil C_j$
- Period $T$ 都是已知
- Message and Signal
- 就是上週算 CAN 的 non preemptive 形式算出的 Response Time
- $Q_i=B_i+\sum_{p_i<p_j}\left\lceil\frac{Q_i+\tau}{T_i}\right\rceil C_j \text{ and } R_{i}=Q_i+C_i$
- Period $T$ 都是已知
- Signal 的 Response Time 就是看他包在哪個 Message 裡面，那個 Message 的 Response Time 就是 Signal 的 Response Time
- Path
- 有了上面兩種的 Response Time，就可以來決定一條路徑上的 Worst Case Response Time
- 例如從 task $\tau_1$ 經過 message $\sigma_1$ 傳到 task $\tau_4$，把中間經過的 worst case response time 加起來
- 然後會有一個給定的 deadline ，上面算出的時間要小於等於這個 deadline

## $s_{i,j}$ 跟 $v_{k,l}$

這兩個在 MILP 的式子裡面會發揮用處，例如 $s_{i,j}$ 決定兩個 task 有沒有在同個 ECU 上，如果沒有的話，在計算 response 的時候其實 $\Sigma$ 裡面有一人不會出現，此時只要在旁邊乘上 $s_{i,j}$ 就可以達到這種效果。

$v_{k,l}$ 也會有類似的作用。

---

# Solved by MILP：Linearization

其實這個概念應該要在制定 variable 跟 constraints 的時候先提及，因為不是所有式子都可以轉成線性的式子；也就是在制定的時候就要同時去想能不能轉成線性的式子。

## Equivelence

下面在轉成線性式子的時候，除了用到 binary 的特性，還會用到 if and only if 的推導，得到 「等價 Equivelence」的式子，例如：

$$
\begin{align}
a+b=0&\Leftrightarrow a=0 \text{ and } b = 0\\
&\Leftrightarrow ab=0\\
a+b>0&\Leftrightarrow a\ne 0\text{ and } b \ne 0\\
\end{align}
$$

## Inequality of three binary

$$
a+b+c\ne 2
$$

可以轉換成：

$$
a+b-c\le 1\text{ and }a-b+c\le 1\text{ and }-a+b+c\le 1
$$

## Ceiling Function

先令：

$$
\text{ceil}(f)=x
$$

然後就可以轉換成：

$$
0\le x-f \le 1
$$

## Multiplication of two binary variables

先令

$$
a\times b =c
$$

然後就可以寫成：

$$
a+b-1\le c \text{ and } c \le a \text{ and } c \le b
$$

## Multiplication of a binary variable $a$ and a real variable $x$

一樣先令

$$
a\times x = y,\ \ y \in \mathbb{R}
$$

接著就可以寫成：

$$
0\le y \le x \text{ and } x - M(1-a) \le y \le Ma
$$

$M$ 是一個很大的常數。

## Scalability Issue

但是實務上問題的規模往往大到 MILP 無法在合理的時間內算出來，所以通常實際上會採用以下的方式來求得某個解：

- 先設定好 signal packing 跟 message priority (和 group assignment)為某個經驗值，
- 求得這樣設定下的 task allocation 跟 task priority 的解
- 接著換成固定剛剛求得的 task allocation 跟 task priority，(group assignment 一樣為假設值)
- 求得 signal packing 跟 message priority 的解
- (最終將 signal packing、message priority、task allocation、task priority 固定成剛剛的解)
- 求得 group assignment

:::warning
但是要注意這樣的做法不一定能得到最佳解，甚至有時候會減少解空間的，使得我們找不到最佳解；但是這樣做我們可以得到合理的時間加速。
group assignment 是沒有提到的部分。
:::

---

# Solved By Simulated Annealing

一樣是考慮那四個 Ingredient

- Solution space
- 也就是上面的四大 variable 的內容
- task 要放哪裡？ signal 要放哪裡？ 每個 task 的 priority？ 每個 message 的 priority？
- Neighborhood structure
- 要怎麼挑出一個解？首先可以看四大 variable 的內容，你想著重哪一項
- 先挑出一項後，再做判斷：
- 如果是 task 要放哪裡，例如把某個 task 從 原本的 ECU 移動到另一個 ECU
- 如果是 signal 要放哪個 message 裡面，也是一樣換位置看看
- 如果是 priority 的話，可以試試看交換兩個 task(message) 的 priority
- Cost Function
- 可以利用剛剛的 path 長度作為 cost
- Annealing schedule
- 溫度要怎麼設，同樣溫度下要跑多少 iteration 也是設計者可以自行根據經驗發揮的地方

---

# 很多 task 放同個 ECU 是好事嗎

雖然同個 ECU 放太多 task 可能會導致 worst case repsonse time 變很大，但是其實同時對於 signal 會有一些好處：

- 如果兩個 signal 在同個 ECU 內，那就不用傳了
- 如果兩個 signal 的 destination 一樣，那麼就可以塞進同個 message 裡面
- 這樣還可以省下 header

---

# TDMA-Based Mapping Problem

既然我們有提到 TDMA-Based 的 Timing Analysis，那麼我們也可以依樣畫葫蘆的，照上面的流程來解 TDMA-Based Mapping Problem。

- 不過由於 TDMA-Based 通常傳輸比較快，所以通常為了避免太複雜，不會做 Signal Packing，也就是一個 signal 就會對應到一個 message。
- 而且由於哪段時間要給誰用的 pattern 都是給定的，所以 message 不再需要有 priority。
- 雖然少了 Signal Packing 跟 message priority，但是要新增處理的就是 scheduling，也就是 time slot 跟 message 的 pattern 要如何設置

## Scheduling

通常來說因為 variables 很有可能也會非常多，所以除了用上面提到的變種版的 MILP 去解，也有可能用 SA 來解。

而用 SA 來解的時候，就可以用上週提到 Synchronous 跟 Asynchronous 的特性來做 Neighborhood 的挑選。

但同時也要注意，如果是有多個 Message 的話，那可能就要小心衝突的問題。

:::danger
不確定由同個 switch 發出的 signal 是不是算同個 message；如果是的話，多個 message 是代表多個 switch 嗎？
:::