Tampere University of Technology

TUTCRIS Research Portal

Data Flow Algorithms for Processors with Vector Extensions: Handling Actors With Internal State

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)21-31
JournalJournal of Signal Processing Systems
Volume87
Issue number1
DOIs
Publication statusPublished - 2017
Publication typeA1 Journal article-refereed

Abstract

Full use of the parallel computation capabilities of present and expected CPUs and GPUs requires use of vector extensions. Yet many actors in data flow systems for digital signal processing have internal state (or, equivalently, an edge that loops from the actor back to itself) that impose serial dependencies between actor invocations that make vectorizing across actor invocations impossible. Ideally, issues of inter-thread coordination required by serial data dependencies should be handled by code written by parallel programming experts that is separate from code specifying signal processing operations. The purpose of this paper is to present one approach for so doing in the case of actors that maintain state. We propose a methodology for using the parallel scan (also known as prefix sum) pattern to create algorithms for multiple simultaneous invocations of such an actor that results in vectorizable code. Two examples of applying this methodology are given: (1) infinite impulse response filters and (2) finite state machines. The correctness and performance of the resulting IIR filters and one class of FSMs are studied.

Keywords

  • Data flow computing, Digital signal processing, Graphics processing units, Parallel algorithms, Vector processors

Publication forum classification

Field of science, Statistics Finland