Conference Papers Year : 2022

Optimal Triangulation on the High Bandwidth Memory Model

Abstract

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.
Fichier principal
Vignette du fichier
Optimal_Triangulation_on_the_High_Bandwidth_Memory_Model.pdf (1) Télécharger le fichier

Dates and versions

lirmm-04928532 , version 1 (04-02-2025)

Identifiers

Cite

Koji Nakano, Victor Poupet. Optimal Triangulation on the High Bandwidth Memory Model. IPDPSW 2022 - IEEE International Parallel and Distributed Processing Symposium Workshops, May 2022, Lyon, France. pp.500-507, ⟨10.1109/IPDPSW55747.2022.00089⟩. ⟨lirmm-04928532⟩
0 View
0 Download

Altmetric

Share

More