Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F07%3APU70793" target="_blank" >RIV/00216305:26230/07:PU70793 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Time- and Space-Efficient Evaluation of Sparse Boolean Functions in Embedded Software

Original language description

The paper addresses software implementation of large sparse systems of Boolean functions. Fast evaluation of such functions with the smallest memory consumption is often required in embedded systems. A new heuristic method of obtaining compact representation of sparse Boolean functions in a form of linked tables is described that can be used for BDD minimization as well. Evaluation of Boolean functions reduces to multiple indirect memory accesses. The method is compared to other techniques like a walk through a BDD or a list search and is illustrated on examples. The presented method is flexible in making trade-offs between performance and memory consumption and may be thus useful for embedded microprocessor or microcontroller software.

Czech name

Časově a prostorově účinné vyhodnocování řídkých boolovských funkcí vestavěným software

Czech description

Článek se zabývá softwarovou implementací velkých řídkých systémů boolovských funkcí.&nbsp; Rychlá evaluace takových funkcí s nejmenším objemem paměti je ve vestavěných systémech často vyžadována. Je popsána nová heuristická metoda získání kompaktní reprezentace řídkých boolovských funkcí ve formě vázaných tabulek, která se dá použít i na minimalizaci BDD. Evaluace boolovských funkcí se redukuje na několik nepřímých přístupů do paměti. Metoda je porovnána s dalšími technikami, jako průchodem přes BDD nebo hledáním v seznamu, a je ilustrována na příkladech. Předložená metoda je pružná při hledání kompromisů mezi výkonností a spotřebou paměti a může být užitečná pro vestavěný software mikroprocesorů a mikrořadičů.&nbsp;&nbsp; <br>

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

<a href="/en/project/GA102%2F07%2F0850" target="_blank" >GA102/07/0850: Design and hardware implementation of a patent-invention machine</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems

ISBN

0-7695-2772-8

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

178-185

Publisher name

IEEE Computer Society

Place of publication

Los Alamitos

Event location

Tuscon, Arizona, USA

Event date

Mar 25, 2007

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—