13th ACM-IEEE International Conference on Formal Methods and Models for System Design
The University of Texas at Austin
September 21-23, 2015
The winners of 2015 MEMOCODE Design Contest:
Rank in Best Cost-Normalized Performance and Highest Performance class: 2- IPM-HPC, 1- Tokyo University
IPM-HPC Team members: Armin Ahmadzadeh, Ehsan Montahaie, Milad Ghafouri, Reza Mirzaei, Saied Rahmani, Farzad Sharif Bakhtiar, Mohsen Gavahi, Rashid Zamanshoar, Hanie Ghasemi, Kianoush Jafari, Saeid Gorgin
Institute for Research in Fundamental Sciences (IPM), Iran
Contest Problem: As in previous years, MEMOCODE’15 will include a design contest, which will pose a computational challenge that participants may solve using hardware or software on FPGAs, GPUs, and CPUs. The conference will sponsor at least one prize with a monetary award for the contest winners. the 2015 challenge is continuous skyline computation that given dataset is not constant and it changes over time. the aim of this contest is to implement a system to efficiently compute the continuous skyline of a large dynamic dataset.
IPM-HPC Solution: Our method makes exhaustive use of CPU and minimizes memory access. we present an efficient parallel continuous Skyline approach. In our suggested method, the dataset points are sorted and pruned based on Manhattan distance. Moreover, we use several optimization methods to optimize memory usage in comparison with naïve implementation. In addition, besides the applied conventional parallelization methods, we partition the time steps based on the number of available cores. The experimental results for a data set that contains 800k points with 7 dimensions show considerable speedup.for more information see the paper.