align.h

Go to the documentation of this file.

#ifndef SEQ_ALIGN_H
#define SEQ_ALIGN_H

#include <ap_int.h>
#include <hls_vector.h>
#include <hls_stream.h>

#include "dp_hls_common.h"
#include "PE.h"
#include "utils.h"
#include "frontend.h"

#ifdef CMAKEDEBUG
#include "./debug.h"
#endif // DBEUG

using namespace hls;

namespace Align
{

    void PrepareLocalQuery(
        char_t (&query)[MAX_QUERY_LENGTH],
        char_t (&local_query)[PE_NUM],
        const idx_t offset);

    void InitializeChunkColScore(
        score_vec_t (&init_col_scr)[PE_NUM],
        stream_of_blocks<dp_mem_block_t> &dp_mem_out);

    void PrepareScoresArr(
        dp_mem_block_t &dp_mem_in,
        score_vec_t (&init_col_scr)[PE_NUM], int id,
        score_vec_t (&last_chunk_scr)[2],
        wavefront_scores_t &up_out,
        wavefront_scores_t &diag_out,
        wavefront_scores_t &left_out);

    template <int PE_NUM_T>
    void PrepareLocals(
        const char_t (&query)[MAX_QUERY_LENGTH],
        char_t (&local_query)[PE_NUM_T],
        score_vec_t (&init_col_scr)[MAX_QUERY_LENGTH],
        chunk_col_scores_inf_t &init_col_scr_local,
        bool (&col_pred)[PE_NUM], const idx_t local_query_len,
        const idx_t idx)
    {
        init_col_scr_local[0] = init_col_scr_local[PE_NUM_T]; // backup the last element from previous chunk
        for (int i = 0; i < PE_NUM_T; i++)
        {
            init_col_scr_local[i + 1] = init_col_scr[idx + i];
            local_query[i] = query[idx + i];
            col_pred[i] = i < local_query_len;
        }
    }

    void InitializeChunkCoordinates(idx_t chunk_row_offset, idx_t chunk_col_offset, hls::vector<idx_t, PE_NUM> &ic, hls::vector<idx_t, PE_NUM> &jc);

    void ArrangeTBP(
        const tbp_vec_t &tbp_in,
        const idx_t &p_col_offset,
        const bool (&predicate)[PE_NUM],
        tbp_t (&chunk_tbp_out)[PE_NUM][TBMEM_SIZE]);

    void ShiftPredicate(bool (&predicate)[PE_NUM], int idx, int query_len, int reference_len);

    void ShiftReference(
        char_t (&local_reference)[PE_NUM], const char_t (&reference)[MAX_REFERENCE_LENGTH],
        int idx, int ref_len);

    void PreserveRowScore(
        score_vec_t (&preserved_row_scr)[MAX_REFERENCE_LENGTH],
        const score_vec_t score_vec,
        const bool predicate_pe_last,
        const idx_t idx);

    void UpdateDPMem(dp_mem_block_t &dp_mem, idx_t i, chunk_col_scores_inf_t &init_col_scr, score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH]);

    void UpdateDPMemShift(dp_mem_block_t &dp_mem);
    void UpdateDPMemSet(dp_mem_block_t &dp_mem, idx_t i, chunk_col_scores_inf_t &init_col_scr, score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH]);

    namespace FindMax
    {
        void ReductionMaxScores(ScorePack (&max)[PE_NUM], ScorePack &chunk_max, idx_t &max_pe);
    };

    namespace Rectangular
    {
        void AlignStatic(
            const char_t (&querys)[MAX_QUERY_LENGTH],
            const char_t (&references)[MAX_REFERENCE_LENGTH],
            const idx_t query_length,
            const idx_t reference_length,
            const Penalties &penalties,
#ifdef LOCAL_TRANSITION_MATRIX
            const type_t (&transitions)[TRANSITION_MATRIX_SIZE][TRANSITION_MATRIX_SIZE],
#endif
            idx_t &tb_i, idx_t &tb_j
#ifndef NO_TRACEBACK
            , tbr_t (&tb_out)[MAX_REFERENCE_LENGTH + MAX_QUERY_LENGTH]
#endif
#ifdef SCORED
            , type_t &score
#endif
#ifdef CMAKEDEBUG
            , Container &debugger
#endif
        );

        void ChunkCompute(
            idx_t chunk_row_offset,
            input_char_block_t &query,
            const char_t (&reference)[MAX_REFERENCE_LENGTH],
            chunk_col_scores_inf_t &init_col_scr,
            score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH],
            idx_t &p_col_offset, idx_t ck_idx,
            idx_t global_query_length, idx_t query_length, idx_t reference_length,
            const bool (&col_pred)[PE_NUM],
            const Penalties &penalties,
#ifdef LOCAL_TRANSITION_MATRIX
            const type_t (&transitions)[PE_NUM][TRANSITION_MATRIX_SIZE][TRANSITION_MATRIX_SIZE],
#endif
            ScorePack (&max)[PE_NUM]
#ifndef NO_TRACEBACK
            , tbp_t (&chunk_tbp_out)[PE_NUM][TBMEM_SIZE]
#endif
#ifdef CMAKEDEBUG
            , Container &debugger
#endif
        );

        void MapPredicate(
            const idx_t wavefront,
            const idx_t ref_len, const idx_t qry_len, // This query length is local query length in chunk, always less than PE_NUM
            bool (&row_pred)[PE_NUM],
            const bool (&col_pred)[PE_NUM],
            bool (&pred)[PE_NUM]);
    }

    namespace Fixed
    {
        void AlignStatic(
            const char_t (&querys)[MAX_QUERY_LENGTH],
            const char_t (&references)[MAX_REFERENCE_LENGTH],
            const idx_t query_length,
            const idx_t reference_length,
            const Penalties &penalties,
#ifdef LOCAL_TRANSITION_MATRIX
            const type_t (&transitions)[TRANSITION_MATRIX_SIZE][TRANSITION_MATRIX_SIZE],
#endif
            idx_t &tb_i, idx_t &tb_j
#ifndef NO_TRACEBACK
            , tbr_t (&tb_out)[MAX_REFERENCE_LENGTH + MAX_QUERY_LENGTH]
#endif
#ifdef SCORED
            , type_t &score
#endif
#ifdef CMAKEDEBUG
            , Container &debugger
#endif
        );

        void ChunkCompute(
            const idx_t chunk_row_offset,
            const input_char_block_t &query,
            const char_t (&reference)[MAX_REFERENCE_LENGTH],
            const chunk_col_scores_inf_t &init_col_scr,
            score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH],
            idx_t p_cols, const idx_t ck_idx,
            idx_t &l_lim_reg, idx_t &u_lim_reg,
            const bool (&col_pred)[PE_NUM],
            const idx_t global_query_length, const idx_t local_query_length, const idx_t reference_length,
            const Penalties &penalties,
#ifdef LOCAL_TRANSITION_MATRIX
            const type_t (&transitions)[PE_NUM][TRANSITION_MATRIX_SIZE][TRANSITION_MATRIX_SIZE],
#endif
            ScorePack (&max)[PE_NUM] // write out so must pass by reference
#ifndef NO_TRACEBACK
            , tbp_t (&chunk_tbp_out)[PE_NUM][TBMEM_SIZE]
#endif
#ifdef CMAKEDEBUG
            ,
            Container &debugger
#endif
        );

        void MapPredicate(
            const idx_t (&local_l_lim)[PE_NUM], const idx_t (&local_u_lim)[PE_NUM],
            const idx_t (&virtual_cols)[PE_NUM], const bool (&col_pred)[PE_NUM],
            bool (&predicate)[PE_NUM]);

        template <int PE_NUM_, int MAX_QUERY_LENGTH_>
        void PrepareLocals(
            const char_t (&query)[MAX_QUERY_LENGTH_],
            const score_vec_t (&init_col_scr)[MAX_QUERY_LENGTH_],
            char_t (&local_query)[PE_NUM_],
            chunk_col_scores_inf_t &init_col_scr_local,
            bool (&col_pred)[PE_NUM_], const idx_t local_query_len,
            const idx_t idx)
        {
            FixedBandingPrepareChunkLocals:
            init_col_scr_local[0] = init_col_scr_local[PE_NUM_]; // backup the last element from previous chunk
            for (int i = 0; i < PE_NUM_; i++)
            {
                init_col_scr_local[i + 1] = init_col_scr[idx + i];
                local_query[i] = query[idx + i];
                col_pred[i] = i < local_query_len;
            }
        }
    }

    void InitializeScores(
        score_vec_t (&init_col_scr)[MAX_QUERY_LENGTH],
        score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH],
        const Penalties &penalties);

    void ChunkMax(ScorePack &max, ScorePack new_scr);

    void UpdatePEOffset(idx_t (&pe_offset)[PE_NUM], bool (&predicate)[PE_NUM]);

    void CopyColScore(chunk_col_scores_inf_t &init_col_scr_local, score_vec_t (&init_col_scr)[MAX_QUERY_LENGTH], idx_t i);

    void UpdateDPMemSep(
        score_vec_t (&dp_mem)[PE_NUM + 1][2],
        score_vec_t (&score_in)[PE_NUM + 1]);

    void PrepareScoreBuffer(
        score_vec_t (&score_buff)[PE_NUM + 1],
        const idx_t i,
        const chunk_col_scores_inf_t(&init_col_scr),
        const score_vec_t (&init_row_scr)[MAX_REFERENCE_LENGTH]);
}

#endif // !SEQ_ALIGN_H