Imperial College London


Faculty of EngineeringDepartment of Computing

Professor of Computer Engineering



+44 (0)20 7594 8313w.luk Website




434Huxley BuildingSouth Kensington Campus






BibTex format

author = {Zhao, W and Fu, H and Yang, G and Luk, W},
doi = {10.1109/FPL.2014.6927506},
title = {Patra: Parallel tree-reweighted message passing architecture},
url = {},
year = {2014}

RIS format (EndNote, RefMan)

AB - © 2014 Technical University of Munich (TUM). Maximum a posteriori probability inference algorithms for Markov Random Field are widely used in many applications, such as computer vision and machine learning. Sequential tree-reweighted message passing (TRW-S) is an inference algorithm which shows good quality in finding optimal solutions. However, the performance of TRW-S in software cannot meet the requirements of many real-time applications, due to the sequential scheme and the high memory, bandwidth and computational costs. This paper proposes Patra, a novel parallel tree-reweighted message passing architecture, which involves a fully pipelined design targeting FPGA technology. We build a hybrid CPU/FPGA system to test the performance of Patra for stereo matching. Experimental results show that Patra provides about 100 times faster than a software implementation of TRW-S, and 12 times faster than a GPU-based message passing algorithm. Compared with an existing design in four FPGAs, we can achieve 2 times speedup in a single FPGA. Moreover, Patra can work at video rate in many cases, such as a rate of 167 frame/sec for a standard stereo matching test case, which makes it promising for many real-time applications.
AU - Zhao,W
AU - Fu,H
AU - Yang,G
AU - Luk,W
DO - 10.1109/FPL.2014.6927506
PY - 2014///
TI - Patra: Parallel tree-reweighted message passing architecture
UR -
ER -