Loughborough University
Browse

File(s) under permanent embargo

Reason: This item is currently closed access.

Finding shuffle words that represent optimal scheduling of shared memory access

journal contribution
posted on 2013-07-15, 14:33 authored by Daniel Reidenbach, Markus L. Schmid
In the present paper, we introduce and study the problem of computing, for any given nite set of words, a shu e word with a minimum so-called scope coincidence degree. The scope coincidence degree is the maximum number of di erent symbols that parenthesise any position in the shu e word. This problem is motivated by an application of a new automaton model and can be regarded as the problem of scheduling shared memory accesses of some parallel processes in a way that minimises the number of memory cells required. We investigate the complexity of this problem and show that it can be solved in polynomial time.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHMID, M.L., 2013. Finding shuffle words that represent optimal scheduling of shared memory access. International Journal of Computer Mathematics, 90 (6), pp.1292-1309.

Publisher

© Taylor & Francis

Version

  • AM (Accepted Manuscript)

Publication date

2013

Notes

This is an Author's Accepted Manuscript of an article published in International Journal of Computer Mathematics [© Taylor & Francis], available online at: http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.698007

ISSN

0020-7160

eISSN

1029-0265

Language

  • en