Search

Abstract A novel parallel algorithm is presented for generating random scale-free networks using the preferential attachment model. The algorithm, named cuPPA, is custom-designed for “single instruction multiple data (SIMD)” style of parallel processing supported by modern processors such as graphical processing units (GPUs). To the best of our knowledge, our algorithm is the first to exploit GPUs, and also the fastest implementation available today, to generate scale-free networks using the preferential attachment model. A detailed performance study is presented to understand the scalability and runtime characteristics of the cuPPA algorithm. Also another version of the algorithm called cuPPA-Hash tailored for multiple GPUs is presented. On a single GPU, the original cuPPA algorithm delivers the best performance, but is challenging to port to multi-GPU implementation. For multi-GPU implementation, cuPPA-Hash has been used as the parallel algorithm to achieve a perfect linear speedup up to 4 GPUs. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, the original cuPPA generates a scale-free network of two billion edges in less than 3 s. On multi-GPU platforms, cuPPA-Hash generates a scale-free network of 16 billion edges in less than 7 s using a machine consisting of 4 NVidia Tesla P100 GPUs.

Distributed programs are often formulated in popular functional frameworks like MapReduce, Spark and Thrill, but writing efficient algorithms for such frameworks is usually a non-trivial task. As the costs of running faulty algorithms at scale can be severe, it is highly desirable to verify their correctness. We propose to employ existing imperative reference implementations as specifications for MapReduce implementations. To this end, we present a novel verification approach in which equivalence between an imperative and a MapReduce implementation is established by a series of program transformations. In this paper, we present how the equivalence framework can be used to prove equivalence between an imperative implementation of the PageRank algorithm and its MapReduce variant. The eight individual transformation steps are individually presented and explained.

Background: Frequent high blood glucose concentrations are associated with increased risks of metabolic diseases. Knowledge about the glycemic response after food intake is essential in relation to human health. The American Association of Cereal Chemists recommends the development of reliable in vitro methods for standardized assessment of the human glycemic response after intake of carbohydrates. Aim: To realize a cost-efficient in vitro–in silico technology to predict reliably the human glycemic concentration curve after intake of different carbohydrate products or meals. Methods: We developed and validated a combined technology based on in vitro mastication of foods, digestion of the carbohydrates, availability for absorption of glycemic saccharides, and (based on these in vitro data as input) in silico prediction of glycemic response curves in humans. Results: The predicted curves were compared with human clinical data for 22 different food products. The results showed a correlation coefficient for glucose iAUC0–120 and glucose Cmax of 0.89 and 0.94, respectively. Also the shape of the curves and tmax were very similar for 18 out of 22 products, while 4 products showed an ‘early’ in vitro tmax compared to the human data. Conclusion: Based on the demonstrated accuracy and predictive quality, this in vitro–in silico technology can be used for the testing of food products on their glycemic response under standardized conditions and may stimulate the production of (s)low carbs for the prevention of metabolic diseases.