多處理機平行程式設計作業bonus2說明（加分題）

# 多處理機平行程式設計作業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$。 請同學使用mpi與pthread共同實作平行化，將mpi的每一個rank創造m個pthread來進行計算，一共n個rank（mpiexec -np n ./bonus2 m)。 judge預設是2個rank 4個pthread 但是助教測試會調整rank與pthread數量在不影響程式speed的情況下，請確保程式能讀取變數並合理的平行化計算。 ### 輸入輸出說明總共 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 注意: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來實做 time out：5s ### 加分方式總成績加2分 ### 繳交格式繳交期限為12/27（五）晚上11點59分在Github上傳一個程式碼檔案以及對應的Makefile檔案，程式碼檔名為學號_bonus2 例如：p12345678_bonus2.c p12345678_bonus2.cpp都可 Makefile就叫Makefile