Efficient Parallel Learning of Linear Dynamical Systems on SMPs


Multi-core processors with ever increasing number of cores per chip are becoming prevalent in modern parallel computing. Our goal is to make use of the multi-core as well as multi-processor architectures to speed up data mining algorithms. Speci´Čücally, we present a parallel algorithm for approximate learning of Linear Dy- namical Systems (LDS), also known as Kalman Filters (KF). LDSs are widely used in time series analysis such as motion capture mod- eling, visual tracking etc. We propose Cut-And-Stitch (CAS), a novel method to handle the data dependencies from the chain struc- ture of hidden variables in LDS, so as to parallelize the EM-based parameter learning algorithm. We implement the algorithm using OpenMP on both a supercomputer and a quad-core commercial desktop. The experimental results show that parallel algorithms us- ing Cut-And-Stitch achieve comparable accuracy and almost linear speedups over the serial version.


Venue, Date, and Time

Venue: 4623 Wean Hall

Date: Monday, Oct 6, 2008

Time: 12:00 noon