5 Search Results for "Agrawal, Ankit"


Document
Contention-Aware Dynamic Memory Bandwidth Isolation with Predictability in COTS Multicores: An Avionics Case Study

Authors: Ankit Agrawal, Gerhard Fohler, Johannes Freitag, Jan Nowotsch, Sascha Uhrig, and Michael Paulitsch

Published in: LIPIcs, Volume 76, 29th Euromicro Conference on Real-Time Systems (ECRTS 2017)


Abstract
Airbus is investigating COTS multicore platforms for safety-critical avionics applications, pursuing helicopter-style autonomous and electric aircraft. These aircraft need to be ultra-lightweight for future mobility in the urban city landscape. As a step towards certification, Airbus identified the need for new methods that preserve the ARINC 653 single core schedule of a Helicopter Terrain Awareness and Warning System (HTAWS) application while scheduling additional safety-critical partitions on the other cores. As some partitions in the HTAWS application are memory-intensive, static memory bandwidth throttling may lead to slow down of such partitions or provide only little remaining bandwidth to the other cores. Thus, there is a need for dynamic memory bandwidth isolation. This poses new challenges for scheduling, as execution times and scheduling become interdependent: scheduling requires execution times as input, which depends on memory latencies and contention from memory accesses of other cores - which are determined by scheduling. Furthermore, execution times depend on memory access patterns. In this paper, we propose a method to solve this problem for slot-based time-triggered systems without requiring application source-code modifications using a number of dynamic memory bandwidth levels. It is NoC and DRAM controller contention-aware and based on the existing interference-sensitive WCET computation and the memory bandwidth throttling mechanism. It constructs schedule tables by assigning partitions and dynamic memory bandwidth to each slot on each core, considering worst case memory access patterns. Then at runtime, two servers - for processing time and memory bandwidth - run on each core, jointly controlling the contention between the cores and the amount of memory accesses per slot. As a proof-of-concept, we use a constraint solver to construct tables. Experiments on the P4080 COTS multicore platform, using a research OS from Airbus and EEMBC benchmarks, demonstrate that our proposed method enables preserving existing schedules on a core while scheduling additional safety-critical partitions on other cores, and meets dynamic memory bandwidth isolation requirements.

Cite as

Ankit Agrawal, Gerhard Fohler, Johannes Freitag, Jan Nowotsch, Sascha Uhrig, and Michael Paulitsch. Contention-Aware Dynamic Memory Bandwidth Isolation with Predictability in COTS Multicores: An Avionics Case Study. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 2:1-2:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2017.2,
  author =	{Agrawal, Ankit and Fohler, Gerhard and Freitag, Johannes and Nowotsch, Jan and Uhrig, Sascha and Paulitsch, Michael},
  title =	{{Contention-Aware Dynamic Memory Bandwidth Isolation with Predictability in COTS Multicores: An Avionics Case Study}},
  booktitle =	{29th Euromicro Conference on Real-Time Systems (ECRTS 2017)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-037-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{76},
  editor =	{Bertogna, Marko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2017.2},
  URN =		{urn:nbn:de:0030-drops-71740},
  doi =		{10.4230/LIPIcs.ECRTS.2017.2},
  annote =	{Keywords: Dynamic memory bandwidth isolation, Safety-critical avionics, COTS multicores}
}
Document
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin

Authors: Neeraj Kayal and Chandan Saha

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
Shpilka and Wigderson (CCC 99) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field F of characteristic zero. We resolve this problem by proving a N^(Omega(d/t)) lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin at most t computing an explicit N-variate polynomial of degree d over F. Meanwhile, Nisan and Wigderson (CC 97) had posed the problem of proving superpolynomial lower bounds for homogeneous depth five arithmetic circuits. Over fields of characteristic zero, we show a lower bound of N^(Omega(sqrt(d))) for homogeneous depth five circuits (resp. also for depth three circuits) with bottom fanin at most N^(u), for any fixed u < 1. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth five circuit has bottom fanin at most N).

Cite as

Neeraj Kayal and Chandan Saha. Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 158-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.CCC.2015.158,
  author =	{Kayal, Neeraj and Saha, Chandan},
  title =	{{Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{158--182},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.158},
  URN =		{urn:nbn:de:0030-drops-50617},
  doi =		{10.4230/LIPIcs.CCC.2015.158},
  annote =	{Keywords: arithmetic circuits, depth three circuits, lower bound, bottom fanin}
}
Document
A Depth-Five Lower Bound for Iterated Matrix Multiplication

Authors: Suman K. Bera and Amit Chakrabarti

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
We prove that certain instances of the iterated matrix multiplication (IMM) family of polynomials with N variables and degree n require N^(Omega(sqrt(n))) gates when expressed as a homogeneous depth-five Sigma Pi Sigma Pi Sigma arithmetic circuit with the bottom fan-in bounded by N^(1/2-epsilon). By a depth-reduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depth-four Sigma Pi Sigma Pi circuits. Our result extends a recent result of Kumar and Saraf, who gave the same N^(Omega(sqrt(n))) lower bound for homogeneous depth-four Sigma Pi Sigma Pi circuits computing IMM. It is analogous to a recent result of Kayal and Saha, who gave the same lower bound for homogeneous Sigma Pi Sigma Pi Sigma circuits (over characteristic zero) with bottom fan-in at most N^(1-epsilon), for the harder problem of computing certain polynomials defined by Nisan-Wigderson designs.

Cite as

Suman K. Bera and Amit Chakrabarti. A Depth-Five Lower Bound for Iterated Matrix Multiplication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 183-197, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.CCC.2015.183,
  author =	{Bera, Suman K. and Chakrabarti, Amit},
  title =	{{A Depth-Five Lower Bound for Iterated Matrix Multiplication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{183--197},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.183},
  URN =		{urn:nbn:de:0030-drops-50622},
  doi =		{10.4230/LIPIcs.CCC.2015.183},
  annote =	{Keywords: arithmetic circuits, iterated matrix multiplication, depth five circuits, lower bound}
}
Document
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs

Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).

Cite as

Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.CCC.2015.323,
  author =	{Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin and Thierauf, Thomas},
  title =	{{Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{323--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323},
  URN =		{urn:nbn:de:0030-drops-50647},
  doi =		{10.4230/LIPIcs.CCC.2015.323},
  annote =	{Keywords: PIT, Hitting-set, Sum of ROABPs, Evaluation Dimension, Rank Concentration}
}
Document
Multi-k-ic Depth Three Circuit Lower Bound

Authors: Neeraj Kayal and Chandan Saha

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
In a multi-k-ic depth three circuit every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi-k-ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta, Kamath, Kayal and Saptharishi [7] on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k.

Cite as

Neeraj Kayal and Chandan Saha. Multi-k-ic Depth Three Circuit Lower Bound. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 527-539, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{kayal_et_al:LIPIcs.STACS.2015.527,
  author =	{Kayal, Neeraj and Saha, Chandan},
  title =	{{Multi-k-ic Depth Three Circuit Lower Bound}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{527--539},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.527},
  URN =		{urn:nbn:de:0030-drops-49395},
  doi =		{10.4230/LIPIcs.STACS.2015.527},
  annote =	{Keywords: arithmetic circuits, multilinear circuits, depth three circuits, lower bound, individual degree}
}
  • Refine by Author
  • 2 Kayal, Neeraj
  • 2 Saha, Chandan
  • 1 Agrawal, Ankit
  • 1 Bera, Suman K.
  • 1 Chakrabarti, Amit
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 arithmetic circuits
  • 3 lower bound
  • 2 depth three circuits
  • 1 COTS multicores
  • 1 Dynamic memory bandwidth isolation
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 4 2015
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail