\relax 
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\citation{cit:uses_FPGA}
\citation{cit:model_GPU}
\citation{cit:intel_combined_xeon}
\citation{cit:bio_paper}
\citation{cit:bio_thesis}
\citation{cit:genet_alg}
\citation{cit:why_faster}
\citation{cit:compare_GPU}
\citation{cit:GPU_compare_sort}
\citation{cit:FPGA_matrix_inv}
\citation{cit:FPGA_AES}
\citation{cit:FPGA_k-means}
\select@language{english}
\@writefile{toc}{\select@language{english}}
\@writefile{lof}{\select@language{english}}
\@writefile{lot}{\select@language{english}}
\@writefile{toc}{\contentsline {title}{Theoretical Model of Computation and Algorithms for FPGA-based Hardware Accelerators\unskip {}}{1}{chapter.1}}
\@writefile{toc}{\authcount {3}}
\@writefile{toc}{\contentsline {author}{Martin Hora\unskip {} \and V\'{a}clav Kon\v {c}ick\'{y}\unskip {} \and Jakub T\v {e}tek\unskip {} }{1}{chapter.1}}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Previous work}{1}{subsection.1.1.1}}
\citation{cit:synch_circ}
\citation{cit:circuit_book}
\citation{cit:intel_combined_xeon}
\citation{cit:RAM_speed}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Our contributions}{2}{subsection.1.1.2}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Preliminaries}{2}{section.1.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Boolean Circuits}{2}{subsection.1.2.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Field Programmable Gate Arrays}{2}{subsection.1.2.2}}
\newlabel{section:fpga}{{2.2}{2}{Field Programmable Gate Arrays\relax }{subsection.1.2.2}{}}
\citation{cit:word_ram}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}I/O model}{3}{subsection.1.2.3}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Model of Computation}{3}{section.1.3}}
\newlabel{section:model}{{3}{3}{Model of Computation\relax }{section.1.3}{}}
\newlabel{th:copy}{{1}{4}{Model of Computation\relax }{theorem.1.3.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Algorithmic Results}{4}{section.1.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Aggregation}{4}{subsection.1.4.1}}
\newlabel{section:aggregation}{{4.1}{4}{Aggregation\relax }{subsection.1.4.1}{}}
\newlabel{problem:aggregation}{{1}{4}{Aggregation\relax }{problem2.1}{}}
\citation{cit:bitonic}
\citation{cit:bitonic}
\citation{cit:opt_sort_netw}
\newlabel{th:aggregation}{{2}{5}{Aggregation\relax }{theorem.1.4.2}{}}
\newlabel{th:bulk:aggregation}{{3}{5}{Aggregation\relax }{theorem.1.4.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Sorting}{5}{subsection.1.4.2}}
\newlabel{section:sorting}{{4.2}{5}{Sorting\relax }{subsection.1.4.2}{}}
\newlabel{problem:pivot}{{2}{5}{Sorting\relax }{problem2.2}{}}
\newlabel{th:pivot}{{4}{5}{Sorting\relax }{theorem.1.4.4}{}}
\citation{cit:bitonic}
\citation{cit:rand_tree_height}
\newlabel{th:pivot:bulk}{{5}{6}{Sorting\relax }{theorem.1.4.5}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Associative operation}{6}{subsection.1.4.3}}
\newlabel{section:assoc_op}{{4.3}{6}{Associative operation\relax }{subsection.1.4.3}{}}
\newlabel{problem:sum}{{3}{6}{Associative operation\relax }{problem2.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Dynamic programs}{7}{subsection.1.4.4}}
\newlabel{section:dynprog}{{4.4}{7}{Dynamic programs\relax }{subsection.1.4.4}{}}
\@writefile{toc}{\contentsline {paragraph}{A dynamic program}{7}{section*.2}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces The grey cell can only depend on the hatched cells in a CULD dynamic program}}{7}{figure.1.1}}
\newlabel{fig:culd_dyn}{{1}{7}{The grey cell can only depend on the hatched cells in a CULD dynamic program\relax }{figure.1.1}{}}
\citation{cit:alg_intro}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Contiguous sequence of cells (grey) depend on a constant number (in this case two) of contiguous sequences of cells (hatched)}}{8}{figure.1.2}}
\newlabel{fig:dyn_dependency}{{2}{8}{Contiguous sequence of cells (grey) depend on a constant number (in this case two) of contiguous sequences of cells (hatched)\relax }{figure.1.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.5}Recursive algorithms}{8}{subsection.1.4.5}}
\newlabel{section:recursive}{{4.5}{8}{Recursive algorithms\relax }{subsection.1.4.5}{}}
\newlabel{def:total}{{3}{8}{Recursive algorithms\relax }{definition.3}{}}
\citation{cit:karatsuba}
\citation{cit:strassen}
\citation{cit:exp_survey,cit:alg_dom_set}
\newlabel{th:PCRAM_and_master}{{9}{9}{Recursive algorithms\relax }{theorem.1.4.9}{}}
\newlabel{simulation}{{4.5}{9}{\textbf {Simulation of RAM or a Turing machine}\relax }{section*.3}{}}
\@writefile{toc}{\contentsline {paragraph}{\textbf  {Simulation of RAM or a Turing machine}}{9}{section*.3}}
\citation{cit:simulate_tm}
\citation{cit:dem_survey}
\citation{cit:book_low_bnd}
\newlabel{thm:RAM_simul}{{10}{10}{\textbf {Simulation of RAM or a Turing machine}\relax }{theorem.1.4.10}{}}
\newlabel{thm:TM_simul}{{11}{10}{\textbf {Simulation of RAM or a Turing machine}\relax }{theorem.1.4.11}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Lower Bounds}{10}{section.1.5}}
\newlabel{section:lower_bounds}{{5}{10}{Lower Bounds\relax }{section.1.5}{}}
\newlabel{cor:low_bnd}{{2}{10}{Lower Bounds\relax }{corollary.2}{}}
\newlabel{thm:predecessor_lb}{{13}{10}{Lower Bounds\relax }{theorem.1.5.13}{}}
\bibstyle{plainnat}
\bibdata{literature}
\bibcite{cit:opt_sort_netw}{{1}{1983}{{Ajtai et~al.}}{{Ajtai, Koml\'{o}s, and Szemer{\'e}di}}}
\bibcite{cit:genet_alg}{{2}{2009}{{Alam}}{{}}}
\bibcite{cit:bitonic}{{3}{1968}{{Batcher}}{{}}}
\bibcite{cit:compare_GPU}{{4}{2008}{{Che et~al.}}{{Che, Li, Sheaffer, Skadron, and Lach}}}
\bibcite{cit:FPGA_AES}{{5}{2003}{{Chodowiec and Gaj}}{{}}}
\bibcite{cit:bio_paper}{{6}{2012}{{Chrysos et~al.}}{{Chrysos, Sotiriades, Rousopoulos, Dollas, Papadopoulos, Kirmitzoglou, Promponas, Theocharides, Petihakis, Lagnel, Vavylis, and Kotoulas}}}
\bibcite{cit:alg_intro}{{7}{2009}{{Cormen and Leiserson}}{{}}}
\bibcite{cit:dem_survey}{{8}{2002}{{Demaine}}{{}}}
\bibcite{cit:GPU_compare_sort}{{9}{2010}{{Grozea et~al.}}{{Grozea, Bankovic, and Laskov}}}
\bibcite{cit:why_faster}{{10}{2004}{{Guo et~al.}}{{Guo, Najjar, Vahid, and Vissers}}}
\bibcite{cit:word_ram}{{11}{1998}{{Hagerup}}{{}}}
\bibcite{cit:synch_circ}{{12}{1977}{{Harper}}{{}}}
\bibcite{cit:intel_combined_xeon}{{13}{2018}{{Huffstetler}}{{}}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Open Problems}{11}{section.1.6}}
\bibcite{cit:FPGA_k-means}{{14}{2011}{{Hussain et~al.}}{{Hussain, Benkrid, Seker, and Erdogan}}}
\bibcite{cit:karatsuba}{{15}{1962}{{Karatsuba and Ofman}}{{}}}
\bibcite{cit:FPGA_matrix_inv}{{16}{2005}{{Karkooti et~al.}}{{Karkooti, Cavallaro, and Dick}}}
\bibcite{cit:model_GPU}{{17}{2014}{{Ma et~al.}}{{Ma, Agrawal, and Chamberlain}}}
\bibcite{cit:bio_thesis}{{18}{2013}{{Mahram}}{{}}}
\bibcite{cit:rand_tree_height}{{19}{2003}{{Reed}}{{}}}
\bibcite{cit:uses_FPGA}{{20}{2017}{{Romoth et~al.}}{{Romoth, Porrmann, and R\IeC {\"u}ckert}}}
\bibcite{cit:RAM_speed}{{21}{2015}{{Sklavos}}{{}}}
\bibcite{cit:strassen}{{22}{1969}{{Strassen}}{{}}}
\bibcite{cit:alg_dom_set}{{23}{2011}{{van Rooij and Bodlaender}}{{}}}
\bibcite{cit:book_low_bnd}{{24}{2008}{{Vitter}}{{}}}
\bibcite{cit:circuit_book}{{25}{1999}{{Vollmer}}{{}}}
\bibcite{cit:exp_survey}{{26}{2003}{{Woeginger}}{{}}}
\bibcite{cit:simulate_tm}{{27}{1996}{{Zwick and Gupta}}{{}}}
\@writefile{toc}{\contentsline {section}{\numberline {A}Simulation of Word-RAM}{12}{section.A.1}}
\newlabel{app_a}{{A}{12}{Simulation of Word-RAM\relax }{section.A.1}{}}