diff options
| -rw-r--r-- | hw3/README.txt | 59 | ||||
| -rw-r--r-- | hw3/alltest.sh.in | 6 | ||||
| -rw-r--r-- | hw3/merger.c | 6 |
3 files changed, 66 insertions, 5 deletions
diff --git a/hw3/README.txt b/hw3/README.txt new file mode 100644 index 0000000..4119a3d --- /dev/null +++ b/hw3/README.txt @@ -0,0 +1,59 @@ + +Compile (Makefile) +------------------ +檔案名稱為 Makefile.或 Makefile.simple，這兩個檔案的內容是相同的。 +輸入 make 會自動轉由 Autotools 編譯並取代為 Autotools 產生的 Makefile， +輸入 make all 編譯，make clean 可清除已編譯的檔案。若無法編譯成功，可 +嘗試輸入 make all CFLAGS= 。 +有些變數可以在執行 make 時更改以符合需求。這個程式必須使用支援 C99 或 C11 的 C +編譯器才能編譯成功，無法使用 C89 或 C++ 編譯器來編譯。 + 可修改的變數： + CC C 編譯器執行檔名，預設是 c99 + CFLAGS 使用者傳給 C 編譯器的參數（不會取代預設的必要參數） + LDFLAGS 使用者傳給 linker 的參數（不會取代預設的必要參數） + +Compile (Autotools) +------------------- +執行 ./configure 即可產生 Makefile，並執行 make 來編譯。如果需要顯示編譯 +時執行的指令，可用 make V=1。輸入 make dist 可將作業打包成 .tar.gz 檔案， +但由於預設的檔名不符合作業要求，需要額外執行 make submit 才能將檔名轉換成 +作業要求的格式。 +執行 make check 可編譯並執行額外的程式來檢查程式運作是否正常。如果只要測試 +執行時間而不在意結果是否正確的話，可設定環境變數 MERGER_NOCHECK 為 1 並 +執行 ./alltest.sh。 + +Testing +------- +(length) = (100) + (length, segment_size) = (100, 100) ... real 0.00 user 0.00 + (length, segment_size) = (100, 50) ... real 0.00 user 0.00 + (length, segment_size) = (100, 20) ... real 0.00 user 0.00 + (length, segment_size) = (100, 10) ... real 0.00 user 0.00 + (length, segment_size) = (100, 4) ... real 0.00 user 0.00 + (length, segment_size) = (100, 1) ... real 0.00 user 0.01 +(length) = (10000) + (length, segment_size) = (10000, 10000) ... real 0.00 user 0.00 + (length, segment_size) = (10000, 5000) ... real 0.00 user 0.01 + (length, segment_size) = (10000, 2000) ... real 0.00 user 0.01 + (length, segment_size) = (10000, 1000) ... real 0.00 user 0.01 + (length, segment_size) = (10000, 400) ... real 0.01 user 0.00 + (length, segment_size) = (10000, 100) ... real 0.01 user 0.00 +(length) = (1000000) + (length, segment_size) = (1000000, 1000000) ... real 0.57 user 0.60 + (length, segment_size) = (1000000, 500000) ... real 0.50 user 0.59 + (length, segment_size) = (1000000, 200000) ... real 0.48 user 0.64 + (length, segment_size) = (1000000, 100000) ... real 0.48 user 0.63 + (length, segment_size) = (1000000, 40000) ... real 0.48 user 0.62 + (length, segment_size) = (1000000, 10000) ... real 0.47 user 0.63 +(length) = (10000000) + (length, segment_size) = (10000000, 10000000) ... real 7.04 user 6.71 + (length, segment_size) = (10000000, 5000000) ... real 6.09 user 6.85 + (length, segment_size) = (10000000, 2000000) ... real 5.73 user 6.96 + (length, segment_size) = (10000000, 1000000) ... real 5.66 user 7.13 + (length, segment_size) = (10000000, 400000) ... real 5.65 user 7.04 + (length, segment_size) = (10000000, 100000) ... real 5.61 user 6.96 + +這些結果取自 ./alltest.sh 的輸出，可看出 user 時間大致相同，但多個 thread +時 real 時間有縮短了一些。我想 user 時間相同是因為 thread 數量並不影響總工 +作量，而在多核心的 CPU 上多個 thread 確實利用了一些同時執行的好處，來節省 +實際執行花費的時間（real time）。 diff --git a/hw3/alltest.sh.in b/hw3/alltest.sh.in index 24c0c82..17ebdca 100644 --- a/hw3/alltest.sh.in +++ b/hw3/alltest.sh.in @@ -11,7 +11,7 @@ runtest () { SI="${3}/test-${1}-ss.in" SO="${3}/test-${1}-ss.out" - if [ -z "$MERGE_NOCHECK" ]; then + if [ -z "$MERGER_NOCHECK" ]; then O="${3}/test-${1}-ss-${2}.out" else O="/dev/null" @@ -25,7 +25,7 @@ runtest () { printf " ... " > /dev/tty time -p sh -c "${B}/merger \"$2\" < \"${SI}\" | tail -n 1 > \"${O}\"" 2>&1 \ | head -n 2 | tr "\n" " " > /dev/tty - if [ -z "$MERGE_NOCHECK" ]; then + if [ -z "$MERGER_NOCHECK" ]; then cmp "${SO}" "${O}" return $? fi @@ -46,6 +46,6 @@ for len in 100 10000 1000000 10000000; do done done -if [ -z "$MERGE_NOCHECK" ]; then +if [ -z "$MERGER_NOCHECK" ]; then rm -rf "${T}" fi diff --git a/hw3/merger.c b/hw3/merger.c index 18f383e..e3a732f 100644 --- a/hw3/merger.c +++ b/hw3/merger.c @@ -72,8 +72,9 @@ static void* task_merge (void* md_generic) { int j = md->mid, jend = md->end; int k = 0; + int_least32_t dup_num = s[i]; int dup_count = 0; - bool is_dup; + bool is_dup = false; while (i < iend && j < jend) { if (s[i] > s[j]) { @@ -85,9 +86,10 @@ static void* task_merge (void* md_generic) { i++, k++; is_dup = false; } else { - if (!is_dup) { + if (!is_dup || dup_num != s[i]) { dup_count++; } + dup_num = s[i]; t[k] = s[i]; i++, k++; t[k] = s[j]; |