---
# System prepended metadata

title: 多處理機平行程式設計 作業bonus2說明（加分題）
tags: [成大多處理機平行程式設計]

---

# 多處理機平行程式設計 作業bonus2說明（加分題）
###### tags: `成大多處理機平行程式設計`
## 題目: 電路滿足性問題
### 題目敘述
一個電路板有很多的元件，這些元件都是一個超大的 AND 閘且固定輸入為 20 位元，而這些元件的輸出會輸入到一個超大的 OR 閘。我們可以用一個數字來表示一個元件的輸入。
給定一個數字 $N$ ，我們可以把這個輸入轉成三進位。在這個三進位表示中，第 $i$ 位數的值代表 $x_{i}$ 輸入的情況，其中 $0$ 代表忽略 $x_{i}$, $1$ 代表直接輸入 $x_{i}$, $2$ 代表輸入加上 NOT 閘 $\overline{x_{i}}$。
以 $4$ 位元輸入為例，我們有 $x_{4}$, $x_{3}$, $x_{2}$, $x_{1}$ 輸入。給定序列 $7$, $63$，可以得到三進位表示式為 $0021$, $2100$，則此電路為 $\overline{x_{2}}x_{1}$ | $\overline{x_{4}}x_{3}$。給定一序列數字來代表多個元件連結在一個 OR 閘的電路，請輸出總共有幾種輸入(數量) 可以使這個電路輸出為 $1$。

<font color="#f00">請同學使用mpi與pthread共同實作平行化，將mpi的每一個rank創造m個pthread來進行計算，一共n個rank（mpiexec -np n ./bonus2 m)。
judge預設是2個rank 4個pthread 但是助教測試會調整rank與pthread數量在不影響程式speed的情況下，請確保程式能讀取變數並合理的平行化計算。</font>

### 輸入輸出說明

總共 4 個測資 (分數各佔 25%)。
輸入一整數 n 代表 AND gate 數量，接著輸入 n 個整數代表各元件，數字範圍介於 $1$ ~ ($3^{20}$ - $1$)。
輸出總共有幾種訊號輸入能使這個電路的輸出為 1。

### 範例輸入1 (提示: $3^{20}$ - $1$)

1
3486784400

### 輸出
1

### 範例輸入2

5
617617617
617617
617
61
7

### 輸出

279808


<font color="#f00">注意:1.要做平行化，同時使用mpi, pthread
$\space$$\space$$\space$$\space$$\space$$\space$$\space$ 2.judge執行命令為mpiexec -np 2 ./bonus2 4，最後測試可能會做調整
$\space$$\space$$\space$$\space$$\space$$\space$$\space$ 3.同學可以參考moodle上的pseudocode來實做</font>
time out：5s

### 加分方式
總成績加2分

### 繳交格式
繳交期限為12/27（五）晚上11點59分
在Github上傳一個程式碼檔案<font color="#f00">以及對應的Makefile檔案</font>，程式碼檔名為 學號_bonus2
例如：p12345678_bonus2.c p12345678_bonus2.cpp都可
Makefile就叫Makefile
