<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T15:34:41Z</responseDate><request verb="GetRecord" identifier="oai:mountainscholar.org:10217/233742" metadataPrefix="dim">https://api.mountainscholar.org/server/oai/request</request><GetRecord><record><header><identifier>oai:mountainscholar.org:10217/233742</identifier><datestamp>2025-12-30T07:21:40Z</datestamp><setSpec>com_10217_100532</setSpec><setSpec>com_10217_100000</setSpec><setSpec>com_10217_100388</setSpec><setSpec>com_10217_100303</setSpec><setSpec>col_10217_182111</setSpec><setSpec>col_10217_100389</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="d0ddc681-8067-42ed-941f-d26ccd061079" confidence="-1">Mondal, Chiranjeb, author</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="5051b77f-11a8-4d34-aac8-4713467d24f0" confidence="-1">Rajopadhye, Sanjay, advisor</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="e075945b-283e-42db-875b-5573b8217e40" confidence="-1">Pouchet, Louis-Noel, committee member</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="d620385f-cac9-45c2-bc12-a4183de61bc3" confidence="-1">Betten, Anton, committee member</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2021-09-06T10:25:06Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2021-09-06T10:25:06Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2021</dim:field>
   <dim:field mdschema="dc" element="identifier">MONDAL_colostate_0053N_16738.pdf</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/10217/233742</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://doi.org/10.25675/3.04956</dim:field>
   <dim:field mdschema="dc" element="description">Zip file contains supplementary BPMax materials.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">RNA-RNA interactions (RRIs) are essential in many biological processes, including gene tran- scription, translation, and localization. They play a critical role in diseases such as cancer and Alzheimer's. An RNA-RNA interaction algorithm uses a dynamic programming algorithm to predict the secondary structure and suffers very high computational time. Its high complexity (Θ(N3M3) in time and Θ(N2M2) in space) makes it both essential and a challenge to parallelize. RRI programs are developed and optimized by hand most of the time, which is prone to human error and costly to develop and maintain. This thesis presents the parallelization of an RRI program - BPMax on a single shared memory CPU platform. From a mathematical specification of the dynamic programming algorithm, we generate highly optimized code that achieves over 100× speedup over the baseline program that uses a standard 'diagonal-by-diagonal' execution order. We achieve 100 GFLOPS, which is about a fourth of our platform's peak theoretical single-precision performance for max-plus computation. The main kernel in the algorithm, whose complexity is Θ(N3M3) attains 186 GFLOPS. We do this with a polyhedral code generation tool, A L P H A Z, which takes user-specified mapping directives and automatically generates optimized C code that enhances parallelism and locality. A L P H A Z allows the user to explore various schedules, memory maps, parallelization approaches, and tiling of the most dominant part of the computation.</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="medium">born digital</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="medium">masters theses</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="medium">ZIP</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="medium">BPMax</dim:field>
   <dim:field mdschema="dc" element="language">English</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">eng</dim:field>
   <dim:field mdschema="dc" element="publisher">Colorado State University. Libraries</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="ispartof">2020-</dim:field>
   <dim:field mdschema="dc" element="rights">Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.</dim:field>
   <dim:field mdschema="dc" element="title">Accelerating the BPMax algorithm for RNA-RNA interaction</dim:field>
   <dim:field mdschema="dc" element="type">Text</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Master of Science (M.S.)</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Masters</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Computer Science</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Colorado State University</dim:field>
   <dim:field mdschema="dcterms" element="rights" qualifier="dpla">This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>