Advanced Computer Architecture by Junjie Wu & Lian Li

Author:Junjie Wu & Lian Li
Language: eng
Format: epub
Publisher: Springer Singapore, Singapore

4 Parallel LDA Training on GPU

4.1 Data Partition

In LDA algorithm, we need not consider the order of documents in a dataset and the order of words in a document. This provides a good theoretical basis to parallelize LDA algorithm. The common data partition scheme is to divide the documents into a number of partitions, and distributing the partitions to different nodes or cores, then all the nodes or cores update their data after synchronization and communication. However, as mentioned in Sect. 2, the number of words in one document may be several times of another document. For synchronization, we must wait for the node or core which has the documents with the most number of words. On GPU architecture, we also face this problem of load imbalance. Therefore, we propose a partition scheme that distribute the data evenly on the threads.

Our data partition scheme is motivated by the following observation: When we sample the documents dataset, we are sampling the words in it, since a document is a vector of words frequency in LDA. So we just put the words in different documents into the same dataset. In each iteration, we just count the number of words of the dataset, denoted as N, and distribute them over K threads. We do not consider the document subscript of the word, so each thread loads N / K words. In CUDA, a kernel can be executed by multiple equally-shaped blocks, and every block has its blockId; one block can have many threads, and every thread has its threadId [10, 11]. the number K of total threads in kernel is calculated by . We count the thread’s id with , every thread loads N / K words ranging form to .

Actually the data partition scheme may cause a problem that the words from one document may be distributed to different threads. So when different threads sample the data on GPU in parallel, it may cause writing conflict. Multiple threads may access the same value of document-topic matrix at the same time when they occasionally process the words of one document simultaneously. We call this document-topic conflict. Besides document-topic conflict, multiple threads may access the same value of the word-topic matrix or topic vector at the same time. When they occasionally process the same word or the same topic simultaneously, we call it word-topic conflict and topic-vector conflict respectively. This issue may lead to wrong inference results and operation failure. In this paper, we use atomic operation to solve this problem, and more details will be described in the next section.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.