Résumé
The High Bandwidth Memory (HBM) model is a theoretical computing model consisting of a logic circuit with a large external memory. Each address of the external memory can store p elements which can be read or written at the same time. Access to p elements stored at a given address in the external memory has a latency of l clock cycles. However, access to any k consecutive addresses can be done only in (k+l-1) clock cycles in a pipeline fashion by burst mode. A hardware algorithm is implemented in a logic circuit of the HBM to solve a particular problem. In this paper, we present an optimal implementation of the O(n 3 )-time dynamic programming algorithm for solving the optimal polygon triangulation (OPT) problem which is a problem to find a triangulation with minimum total weight of an input convex n-gon with weighted cords. We assume that the input weight matrix of a convex n-gon is stored in the external memory of the HBM model. Our hardware algorithm implemented in the logic circuit of size O(s 2 ) operates on it and computes the optimal polygon triangulation of the input polygon in O( n 3 sp + n 3 s 2 + n 3 s 3 l) time. We also provide a theoretical proof showing that any hardware algorithm in a logic circuit of size O(s 2 ) takes at least Ω( n 3 sp + n 3 s 2 ) time to solve the OPT problem. Thus, our implementation is optimal whenever s 2 ≥ lp or s ≥ l, and this optimality condition is always satisfied from a practical point of view.