Mercurial > hg > Papers > 2018 > parusu-master

Binary file paper/fig/putSynchronizedQueue1.graffle has changed
Binary file paper/fig/putSynchronizedQueue1.pdf has changed
--- a/paper/fig/putSynchronizedQueue1.xbb	Wed Jan 24 02:43:02 2018 +0900
+++ b/paper/fig/putSynchronizedQueue1.xbb	Wed Jan 24 03:27:17 2018 +0900
@@ -1,8 +1,8 @@
 %%Title: fig/putSynchronizedQueue1.pdf
 %%Creator: extractbb 20170318
-%%BoundingBox: 0 0 809 301
-%%HiResBoundingBox: 0.000000 0.000000 809.000000 301.000000
+%%BoundingBox: 0 0 746 301
+%%HiResBoundingBox: 0.000000 0.000000 746.000000 301.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Tue Jan 23 18:39:37 2018
+%%CreationDate: Wed Jan 24 02:45:08 2018
Binary file paper/fig/putSynchronizedQueue2.pdf has changed
--- a/paper/fig/putSynchronizedQueue2.xbb	Wed Jan 24 02:43:02 2018 +0900
+++ b/paper/fig/putSynchronizedQueue2.xbb	Wed Jan 24 03:27:17 2018 +0900
@@ -1,8 +1,8 @@
 %%Title: fig/putSynchronizedQueue2.pdf
 %%Creator: extractbb 20170318
-%%BoundingBox: 0 0 870 391
-%%HiResBoundingBox: 0.000000 0.000000 870.000000 391.000000
+%%BoundingBox: 0 0 825 391
+%%HiResBoundingBox: 0.000000 0.000000 825.000000 391.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Wed Jan 24 02:38:57 2018
+%%CreationDate: Wed Jan 24 02:45:08 2018
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/fig/sendTask.xbb	Wed Jan 24 03:27:17 2018 +0900
@@ -0,0 +1,8 @@
+%%Title: fig/sendTask.pdf
+%%Creator: extractbb 20170318
+%%BoundingBox: 0 0 1028 162
+%%HiResBoundingBox: 0.000000 0.000000 1028.000000 162.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Sun Jan 21 06:07:39 2018
+
Binary file paper/fig/takeSynchronizedQueue1.pdf has changed
--- a/paper/fig/takeSynchronizedQueue1.xbb	Wed Jan 24 02:43:02 2018 +0900
+++ b/paper/fig/takeSynchronizedQueue1.xbb	Wed Jan 24 03:27:17 2018 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 571.000000 202.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Tue Jan 23 17:23:41 2018
+%%CreationDate: Wed Jan 24 02:45:08 2018
Binary file paper/fig/takeSynchronizedQueue2.graffle has changed
Binary file paper/fig/takeSynchronizedQueue2.pdf has changed
--- a/paper/fig/takeSynchronizedQueue2.xbb	Wed Jan 24 02:43:02 2018 +0900
+++ b/paper/fig/takeSynchronizedQueue2.xbb	Wed Jan 24 03:27:17 2018 +0900
@@ -1,8 +1,8 @@
 %%Title: fig/takeSynchronizedQueue2.pdf
 %%Creator: extractbb 20170318
-%%BoundingBox: 0 0 660 202
-%%HiResBoundingBox: 0.000000 0.000000 660.000000 202.000000
+%%BoundingBox: 0 0 561 202
+%%HiResBoundingBox: 0.000000 0.000000 561.000000 202.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Tue Jan 23 17:23:41 2018
+%%CreationDate: Wed Jan 24 02:45:08 2018
Binary file paper/master_paper.pdf has changed
--- a/paper/parallelism_gears.tex	Wed Jan 24 02:43:02 2018 +0900
+++ b/paper/parallelism_gears.tex	Wed Jan 24 03:27:17 2018 +0900
@@ -136,7 +136,15 @@

 この破綻は末尾の要素が必ず末尾を示していると仮定しているためである。
 しかし、データ挿入の際は2度の CAS の間に他のスレッドが割り込む場合がある。
-そこで、末尾の要素は必ず末尾を示す
+そこで、末尾の要素は必ずしも末尾を示さないと仮定して要素の取出しと挿入の処理を記述する。
+\refcode{takeSynchronizedQueue} が要素の挿入の処理の一部である。
+末尾の要素が末尾を示さない場合の処理は\refcode{takeSynchronizedQueue} の 45-48 行目に記述している。
+変数 nextElement は 末尾要素の次の要素を示しており、NULL ではない場合は末尾を差していない状態ということになる。
+その場合は、末尾の要素をnextElement に CAS を行う。
+この処理は要素の取り出しを行う際にも行われる。
+
+\lstinputlisting[caption=SynchronizedQueue による要素の挿入, label=code:takeSynchronizedQueue]{./src/takeSynchronizedQueue.cbc}
+
 \section{依存関係の解決}
 \section{並列処理の記述}
 \section{Iterator}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/reference.bib	Wed Jan 24 03:27:17 2018 +0900
@@ -0,0 +1,92 @@
+@article{moggi-monad,
+    author     = {Moggi, Eugenio},
+    title      = {Notions of Computation and Monads},
+    journal    = {Inf. Comput.},
+    issue_date = {July 1991},
+    volume     = {93},
+    number     = {1},
+    month      = jul,
+    year       = {1991},
+    issn       = {0890-5401},
+    pages      = {55--92},
+    numpages   = {38},
+    url        = {http://dx.doi.org/10.1016/0890-5401(91)90052-4},
+    doi        = {10.1016/0890-5401(91)90052-4},
+    acmid      = {116984},
+    publisher  = {Academic Press, Inc.},
+    address    = {Duluth, MN, USA},
+}
+
+@inproceedings{nobu-prosym,
+    author = "大城,信康 and 河野,真治",
+    title = "Continuation based C の GCC4.6 上の実装について",
+    booktitle = "第53回プログラミング・シンポジウム予稿集",
+    year  = "2012",
+    volume = "2012",
+    number = "",
+    pages = "69--78",
+    month = "jan"
+}
+
+@inproceedings{mitsuki-prosym,
+    author = "宮城,光希 and 河野,真治",
+    title = "Code Gear と Data Gear を持つ Gears OS の設計",
+    booktitle = "第59回プログラミング・シンポジウム予稿集",
+    year  = "2018",
+    volume = "2018",
+    number = "",
+    pages = "69--78",
+    month = "jan"
+}
+
+@article{kaito-lola,
+    author  = "Kaito, Tokumori and Shinji, Kono",
+    title   = "Implementing Continuation based language in LLVM and Clang",
+    journal = "LOLA 2015, Kyoto",
+    month   = "July",
+    year    =  2015
+
+}
+
+@article{kkb-sigos,
+    author  = "小久保,翔平 and 伊波,立樹 and 河野,真治",
+    title   = "Monad に基づくメタ計算を基本とする Gears OS の設計",
+    journal = "第133回情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month   = "May",
+    year    = 2015
+}
+
+@article{parusu-sigos,
+    author  = "伊波,立樹 and 東恩納, 琢偉 and 河野,真治",
+    title   = "Code Gear、 Data Gear に基づく OS のプロトタイプ",
+    journal = "第137回情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month   = "May",
+    year    = 2016
+}
+
+@misc{opencl,
+    title = {OpenCL | NVIDIA Developer},
+    howpublished = {\url{https://developer.nvidia.com/opencl}},
+    note = {Accessed: 2016/02/06(Mon)}
+}
+
+@misc{cuda,
+    title = {CUDA Zone | NVIDIA Developer},
+    howpublished = {\url{https://developer.nvidia.com/cuda-zone}},
+    note = {Accessed: 2016/02/06(Mon)}
+}
+
+
+@mastersthesis{utah-master,
+    author = "徳森海斗",
+    title  = "LLVM Clang 上の Continuation based C コンパイラ の改良",
+    school = "琉球大学 大学院理工学研究科 情報工学専攻",
+    year   = "2016"
+}
+
+@mastersthesis{kkb-master,
+    author = "小久保 翔平",
+    title  = "Code Segment と Data Segment を持つ Gears OS の 設計",
+    school = "琉球大学 大学院理工学研究科 情報工学専攻",
+    year   = "2016"
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/synchronizedQueue.h	Wed Jan 24 03:27:17 2018 +0900
@@ -0,0 +1,11 @@
+struct SynchronizedQueue {
+    struct Element* top;
+    struct Element* last;
+    struct Atomic* atomic;
+};
+
+// Singly Linked List element
+struct Element {
+    union Data* top;
+    struct Element* next;
+};
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/takeSynchronizedQueue.cbc	Wed Jan 24 03:27:17 2018 +0900
@@ -0,0 +1,97 @@
+
+#include "../context.h"
+#interface "Queue.h"
+#interface "Atomic.h"
+
+#include <stdio.h>
+
+/*
+ * Non-blocking queue of Paper: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms(https://www.research.ibm.com/people/m/michael/podc-1996.pdf).
+ */
+
+Queue* createSynchronizedQueue(struct Context* context) {
+    struct Queue* queue = new Queue();
+    struct SynchronizedQueue* synchronizedQueue = new SynchronizedQueue();
+    synchronizedQueue->top = new Element(); // allocate a free node
+    synchronizedQueue->top->next = NULL;
+    synchronizedQueue->last = synchronizedQueue->top;
+    synchronizedQueue->atomic = createAtomicReference(context);
+    queue->queue = (union Data*)synchronizedQueue;
+    queue->take  = C_takeSynchronizedQueue;
+    queue->put  = C_putSynchronizedQueue;
+    queue->isEmpty = C_isEmptySynchronizedQueue;
+    queue->clear = C_clearSynchronizedQueue;
+    return queue;
+}
+
+__code clearSynchronizedQueue(struct SynchronizedQueue* queue, __code next(...)) {
+    struct Element* top = queue->top;
+    struct Atomic* atomic = queue->atomic;
+    goto atomic->checkAndSet(&queue->top, top, NULL, next(...), clearSynchronizedQueue);
+}
+
+__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
+    Element* element = new Element();
+    element->data = data;
+    element->next = NULL;
+    Element* last = queue->last;
+    Element* nextElement = last->next;
+    if (last != queue->last) {
+        goto putSynchronizedQueue();
+    }
+    if (nextElement == NULL) {
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&last->next, nextElement, element, next(...), putSynchronizedQueue);
+    } else { // wrong last element
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&queue->last, last, nextElement, putSynchronizedQueue, putSynchronizedQueue);
+    }
+}
+
+__code takeSynchronizedQueue(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) {
+    struct Element* top = queue->top;
+    struct Element* last = queue->last;
+    struct Element* nextElement = top->next;
+    if (top != queue->top) {
+        goto takeSynchronizedQueue();
+    }
+    if (top == last) {
+        if (nextElement != NULL) {
+            struct Atomic* atomic = queue->atomic;
+            goto atomic->checkAndSet(&queue->last, last, nextElement, takeSynchronizedQueue, takeSynchronizedQueue);
+        }
+    } else {
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&queue->top, top, nextElement, takeSynchronizedQueue1, takeSynchronizedQueue);
+    }
+    goto takeSynchronizedQueue();
+}
+
+__code takeSynchronizedQueue1(struct SynchronizedQueue* queue, __code next(union Data* data, ...), struct Element* nextElement) {
+    data = nextElement->data;
+    goto next(data, ...);
+}
+
+__code takeSynchronizedQueue1_stub(struct Context* context) {
+	SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue);
+	enum Code next = Gearef(context, Queue)->next;
+	Data** O_data = &Gearef(context, Queue)->data;
+	goto takeSynchronizedQueue1(context,
+                                queue,
+                                next,
+                                O_data,
+                                (struct Element*)Gearef(context, Atomic)->newData);
+}
+
+__code isEmptySynchronizedQueue(struct SynchronizedQueue* queue, __code next(...), __code whenEmpty(...)) {
+    struct Element* top = queue->top;
+    struct Element* last = queue->last;
+    struct Element* nextElement = top->next;
+    if (top != queue->top) {
+        goto isEmptySynchronizedQueue();
+    }
+    if (top == last && nextElement == NULL) {
+        goto whenEmpty(...);
+    }
+    goto next(...);
+}