Delay optimization of linear depth Boolean circuits with prescribed input arrival times
type: Item
instance of: scholarly article
title: Delay optimization of linear depth Boolean circuits with prescribed input arrival times
zbMATH Open document ID: 1130.94338
author: Dieter Rautenbach
author: Christian Szegedy
author: Jürgen Werber
published in: Journal of Discrete Algorithms
publication date: 2007-02-14T00:00:00Z
review text: We consider boolean circuits \(C\) over the basis \(\Omega=\{\lor,\land\}\) with inputs \(x_1, x_2,\ldots, x_n\) for which arrival times \(t_1,t_2,\ldots,t_n\in\mathbb{N}_0\) are given. For \(1\leq i\leq n\) we define the delay of \(x_i\) in \(C\) as the sum of \(t_i\) and the number of gates on a longest directed path in \(C\) starting at \(x_i\). The delay of \(C\) is defined as the maximum delay of an input. Given a function of the form \[ f(x_1,x_2,\ldots, x_n)=g_{n-1}(g_{n-2}(\ldots g_3(g_2(g_1(x_1,x_2),x_3),x_4),\ldots ),x_{n-1}),x_n) \] where \(g_j\in \Omega\) for \(1\leq j\leq n-1\) and arrival times for \(x_1,x_2,\ldots x_n\), we describe a cubic-time algorithm that determines a circuit for \(f\) over \(\Omega\) that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5126386
zbMATH Keywords: circuit
zbMATH Keywords: straight-line program
zbMATH Keywords: depth
zbMATH Keywords: delay
zbMATH Keywords: computer arithmetic
zbMATH Keywords: VLSI design
MaRDI profile type: Publication
full work available at URL: j.jda.2005.06.006
OpenAlex ID: W2025635553
cites work: On the Addition of Binary Numbers
cites work: Parallel Prefix Computation
cites work: The delay of circuits whose inputs have specified arrival times
cites work: Q4344138
cites work: Q3999183
cites work: Q3762226
cites work: On the Time Required to Perform Addition
DOI: 10.1016/J.JDA.2005.06.006
description: scientific article; zbMATH DE number 5126386