31009380971

Committed 05 Aug 2026 01:15PM UTC coverage: 65.103% (+0.1%) from 65.005%

Build # 31009380971

Build Type

Pull #814

github

Committed by

web-flow

Commit Message

Merge 268a080ae into 7d5b198bd

Pull Request Pull Request #814: Adds GPU reduce dispatchers

Coverage Stats

409 of 663 new or added lines in 18 files covered. (61.69%)

145 existing lines in 6 files now uncovered.

46693 of 71722 relevant lines covered (65.1%)

713.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

73.87

/opt/src/transformations/offloading/cuda_parallelize_nested_map.cpp

#include "sdfg/transformations/offloading/cuda_parallelize_nested_map.h"

#include <sdfg/analysis/loop_analysis.h>
#include "sdfg/exceptions.h"
#include "sdfg/structured_control_flow/reduce.h"
#include "sdfg/symbolic/symbolic.h"
#include "sdfg/targets/cuda/cuda.h"
#include "sdfg/targets/gpu/gpu_map_utils.h"
#include "sdfg/types/pointer.h"
#include "sdfg/types/scalar.h"

namespace sdfg {
namespace transformations {

CUDAParallelizeNestedMap::CUDAParallelizeNestedMap(structured_control_flow::StructuredLoop& loop, size_t block_size)
    : loop_(loop), block_size_(block_size) {}

std::string CUDAParallelizeNestedMap::name() const { return "CUDAParallelizeNestedMap"; }

bool CUDAParallelizeNestedMap::
    can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    if (dynamic_cast<structured_control_flow::Map*>(&loop_) == nullptr &&
        dynamic_cast<structured_control_flow::Reduce*>(&loop_) == nullptr) {
        return false;
    }

    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();

    // Condition: Check if map is not yet parallelized with CUDA
    if (loop_.schedule_type().value() != ScheduleType_Sequential::value()) {
        return false;
    }

    // Condition: a nested Reduce can only be offloaded when every accumulator is a
    // device-resident pointer to a scalar whose type the atomics baseline supports.
    // Privatize + atomic merge (native atomicAdd or a CAS loop) is only defined for
    // 32/64-bit numeric types, so bool and 8/16-bit accumulators (e.g. torch.any /
    // torch.all over bool) must stay sequential.
    if (auto* reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {
        auto& sdfg = builder.subject();
        for (auto& reduction : reduce->reductions()) {
            auto& type = sdfg.type(reduction.container);
            auto* ptr = dynamic_cast<const types::Pointer*>(&type);
            if (ptr == nullptr || !ptr->has_pointee_type()) {
                return false;
            }
            auto* scalar = dynamic_cast<const types::Scalar*>(&ptr->pointee_type());
            if (scalar == nullptr) {
                return false;
            }
            auto prim = scalar->primitive_type();
            const bool numeric = types::is_floating_point(prim) || types::is_signed(prim) || types::is_unsigned(prim);
            const size_t width = types::bit_width(prim);
            if (!numeric || (width != 32 && width != 64)) {
                return false;
            }
        }
    }

    // Condition: Check if parent loop exists
    auto parent = loop_analysis.parent_loop(&loop_);
    if (parent == nullptr) {
        return false;
    }

    // Condition: Check if parent loop is a CUDA map, and not Z dimension (final dimension)
    if (auto map = dyn_cast<structured_control_flow::Map*>(parent)) {
        if (map->schedule_type().value() != cuda::ScheduleType_CUDA::value()) {
            return false;
        }
        if (cuda::ScheduleType_CUDA::dimension(map->schedule_type()) == cuda::CUDADimension::Z) {
            return false;
        }
        auto parent_indvar = map->indvar();
        auto ancestor = parent;
        while (ancestor) {
            if (auto map_ancestor = dyn_cast<structured_control_flow::Map*>(ancestor)) {
                parent_indvar = map_ancestor->indvar();
                for (auto& arg : symbolic::atoms(loop_.condition())) {
                    if (symbolic::eq(arg, parent_indvar)) {
                        return false;
                    }
                }
            }
            ancestor = loop_analysis.parent_loop(ancestor);
        }
    } else {
        return false;
    }

    // Note: arbitrary `init` and `stride` are permitted. The CUDA dispatcher
    // emits `<map.indvar> = init + thread_flat_id * stride`, so the body sees
    // the natural strided value; `num_iterations()` accounts for both when
    // computing the grid geometry.

    // Condition: Parallelizing this loop must not introduce a data race. Folding a new
    // grid dimension distributes this loop's iterations across the new threads and
    // re-runs every unguarded sibling on each of them, with no grid-wide barrier. That
    // races when this loop produces a shared container a sibling consumes (a reduction
    // accumulator -> consumer, e.g. softmax) or when a sibling read-modify-writes a
    // shared container. Such a loop must be parallelized differently or left sequential.
    if (gpu::nested_parallelization_is_unsafe(loop_, analysis_manager)) {
        return false;
    }

    // Condition: Resulting CUDA grid dimension must not exceed hardware limits.
    // Y and Z grid dimensions are limited to 65535.
    auto num_iters = loop_.num_iterations();
    if (!num_iters.is_null() && SymEngine::is_a<SymEngine::Integer>(*num_iters)) {
        int64_t iters = SymEngine::down_cast<const SymEngine::Integer&>(*num_iters).as_int();
        int64_t block = static_cast<int64_t>(block_size_);
        int64_t grid_size = (iters + block - 1) / block;

        constexpr int64_t max_grid_dim_yz = 65535;
        if (grid_size > max_grid_dim_yz) {
            return false;
        }
    }

    return true;
}

void CUDAParallelizeNestedMap::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {
    auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();
    auto parent = loop_analysis.parent_loop(&loop_);

    auto parent_dim =
        cuda::ScheduleType_CUDA::dimension(static_cast<structured_control_flow::Map*>(parent)->schedule_type());

    cuda::CUDADimension child_dim;
    if (parent_dim == cuda::CUDADimension::X) {
        child_dim = cuda::CUDADimension::Y;
    } else if (parent_dim == cuda::CUDADimension::Y) {
        child_dim = cuda::CUDADimension::Z;
    } else {
        throw InvalidSDFGException("Parent loop is Z dimension, cannot parallelize nested map.");
    }

    auto new_schedule = cuda::ScheduleType_CUDA::create();
    cuda::ScheduleType_CUDA::dimension(new_schedule, child_dim);
    cuda::ScheduleType_CUDA::block_size(new_schedule, symbolic::integer(block_size_));

    builder.update_schedule_type(loop_, new_schedule);
}

void CUDAParallelizeNestedMap::to_json(nlohmann::json& j) const {
    j["transformation_type"] = this->name();
    j["parameters"] = nlohmann::json::object();
    j["parameters"]["block_size"] = block_size_;

    serializer::JSONSerializer ser_flat(false);
    j["subgraph"] = nlohmann::json::object();
    j["subgraph"]["0"] = nlohmann::json::object();
    ser_flat.serialize_node(j["subgraph"]["0"], loop_);
}

CUDAParallelizeNestedMap CUDAParallelizeNestedMap::
    from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {
    // Prefer the embedding-compatible representation (subgraph/parameters),
    // but fall back to legacy fields (loop/block_size) if needed.
    const auto& subgraph = j.at("subgraph");
    const auto& node_desc = subgraph.at("0");
    size_t loop_id = node_desc.at("element_id").get<size_t>();

    size_t block_size = j.at("parameters").at("block_size").get<size_t>();
    auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(builder.find_element_by_id(loop_id));
    if (!loop) {
        throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " is not a loop.");
    }
    return CUDAParallelizeNestedMap(*loop, block_size);
}

} // namespace transformations
} // namespace sdfg

1	#include "sdfg/transformations/offloading/cuda_parallelize_nested_map.h"
2
3	#include <sdfg/analysis/loop_analysis.h>
4	#include "sdfg/exceptions.h"
5	#include "sdfg/structured_control_flow/reduce.h"
6	#include "sdfg/symbolic/symbolic.h"
7	#include "sdfg/targets/cuda/cuda.h"
8	#include "sdfg/targets/gpu/gpu_map_utils.h"
9	#include "sdfg/types/pointer.h"
10	#include "sdfg/types/scalar.h"
11
12	namespace sdfg {
13	namespace transformations {
14
15	CUDAParallelizeNestedMap::CUDAParallelizeNestedMap(structured_control_flow::StructuredLoop& loop, size_t block_size)
16	: loop_(loop), block_size_(block_size) {}	19✔
17
18	std::string CUDAParallelizeNestedMap::name() const { return "CUDAParallelizeNestedMap"; }	3✔
19
20	bool CUDAParallelizeNestedMap::
21	can_be_applied(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	15✔
22	if (dynamic_cast<structured_control_flow::Map*>(&loop_) == nullptr &&	15✔
23	dynamic_cast<structured_control_flow::Reduce*>(&loop_) == nullptr) {	15✔
NEW 24	return false;	×
NEW 25	}	×
26
27	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	15✔
28
29	// Condition: Check if map is not yet parallelized with CUDA
30	if (loop_.schedule_type().value() != ScheduleType_Sequential::value()) {	15✔
31	return false;	1✔
32	}	1✔
33
34	// Condition: a nested Reduce can only be offloaded when every accumulator is a
35	// device-resident pointer to a scalar whose type the atomics baseline supports.
36	// Privatize + atomic merge (native atomicAdd or a CAS loop) is only defined for
37	// 32/64-bit numeric types, so bool and 8/16-bit accumulators (e.g. torch.any /
38	// torch.all over bool) must stay sequential.
39	if (auto* reduce = dynamic_cast<structured_control_flow::Reduce*>(&loop_)) {	14✔
NEW 40	auto& sdfg = builder.subject();	×
NEW 41	for (auto& reduction : reduce->reductions()) {	×
NEW 42	auto& type = sdfg.type(reduction.container);	×
NEW 43	auto* ptr = dynamic_cast<const types::Pointer*>(&type);	×
NEW 44	if (ptr == nullptr \|\| !ptr->has_pointee_type()) {	×
NEW 45	return false;	×
NEW 46	}	×
NEW 47	auto* scalar = dynamic_cast<const types::Scalar*>(&ptr->pointee_type());	×
NEW 48	if (scalar == nullptr) {	×
NEW 49	return false;	×
NEW 50	}	×
NEW 51	auto prim = scalar->primitive_type();	×
NEW 52	const bool numeric = types::is_floating_point(prim) \|\| types::is_signed(prim) \|\| types::is_unsigned(prim);	×
NEW 53	const size_t width = types::bit_width(prim);	×
NEW 54	if (!numeric \|\| (width != 32 && width != 64)) {	×
NEW 55	return false;	×
NEW 56	}	×
NEW 57	}	×
NEW 58	}	×
59
60	// Condition: Check if parent loop exists
61	auto parent = loop_analysis.parent_loop(&loop_);	14✔
62	if (parent == nullptr) {	14✔
63	return false;	1✔
64	}	1✔
65
66	// Condition: Check if parent loop is a CUDA map, and not Z dimension (final dimension)
67	if (auto map = dyn_cast<structured_control_flow::Map*>(parent)) {	13✔
68	if (map->schedule_type().value() != cuda::ScheduleType_CUDA::value()) {	13✔
69	return false;	1✔
70	}	1✔
71	if (cuda::ScheduleType_CUDA::dimension(map->schedule_type()) == cuda::CUDADimension::Z) {	12✔
72	return false;	1✔
73	}	1✔
74	auto parent_indvar = map->indvar();	11✔
75	auto ancestor = parent;	11✔
76	while (ancestor) {	24✔
77	if (auto map_ancestor = dyn_cast<structured_control_flow::Map*>(ancestor)) {	13✔
78	parent_indvar = map_ancestor->indvar();	12✔
79	for (auto& arg : symbolic::atoms(loop_.condition())) {	14✔
80	if (symbolic::eq(arg, parent_indvar)) {	14✔
81	return false;	×
82	}	×
83	}	14✔
84	}	12✔
85	ancestor = loop_analysis.parent_loop(ancestor);	13✔
86	}	13✔
87	} else {	11✔
88	return false;	×
89	}	×
90
91	// Note: arbitrary `init` and `stride` are permitted. The CUDA dispatcher
92	// emits `<map.indvar> = init + thread_flat_id * stride`, so the body sees
93	// the natural strided value; `num_iterations()` accounts for both when
94	// computing the grid geometry.
95
96	// Condition: Parallelizing this loop must not introduce a data race. Folding a new
97	// grid dimension distributes this loop's iterations across the new threads and
98	// re-runs every unguarded sibling on each of them, with no grid-wide barrier. That
99	// races when this loop produces a shared container a sibling consumes (a reduction
100	// accumulator -> consumer, e.g. softmax) or when a sibling read-modify-writes a
101	// shared container. Such a loop must be parallelized differently or left sequential.
102	if (gpu::nested_parallelization_is_unsafe(loop_, analysis_manager)) {	11✔
103	return false;	1✔
104	}	1✔
105
106	// Condition: Resulting CUDA grid dimension must not exceed hardware limits.
107	// Y and Z grid dimensions are limited to 65535.
108	auto num_iters = loop_.num_iterations();	10✔
109	if (!num_iters.is_null() && SymEngine::is_a<SymEngine::Integer>(*num_iters)) {	10✔
110	int64_t iters = SymEngine::down_cast<const SymEngine::Integer&>(*num_iters).as_int();	8✔
111	int64_t block = static_cast<int64_t>(block_size_);	8✔
112	int64_t grid_size = (iters + block - 1) / block;	8✔
113
114	constexpr int64_t max_grid_dim_yz = 65535;	8✔
115	if (grid_size > max_grid_dim_yz) {	8✔
116	return false;	1✔
117	}	1✔
118	}	8✔
119
120	return true;	9✔
121	}	10✔
122
123	void CUDAParallelizeNestedMap::apply(builder::StructuredSDFGBuilder& builder, analysis::AnalysisManager& analysis_manager) {	5✔
124	auto& loop_analysis = analysis_manager.get<analysis::LoopAnalysis>();	5✔
125	auto parent = loop_analysis.parent_loop(&loop_);	5✔
126
127	auto parent_dim =	5✔
128	cuda::ScheduleType_CUDA::dimension(static_cast<structured_control_flow::Map*>(parent)->schedule_type());	5✔
129
130	cuda::CUDADimension child_dim;	5✔
131	if (parent_dim == cuda::CUDADimension::X) {	5✔
132	child_dim = cuda::CUDADimension::Y;	4✔
133	} else if (parent_dim == cuda::CUDADimension::Y) {	4✔
134	child_dim = cuda::CUDADimension::Z;	1✔
135	} else {	1✔
136	throw InvalidSDFGException("Parent loop is Z dimension, cannot parallelize nested map.");	×
137	}	×
138
139	auto new_schedule = cuda::ScheduleType_CUDA::create();	5✔
140	cuda::ScheduleType_CUDA::dimension(new_schedule, child_dim);	5✔
141	cuda::ScheduleType_CUDA::block_size(new_schedule, symbolic::integer(block_size_));	5✔
142
143	builder.update_schedule_type(loop_, new_schedule);	5✔
144	}	5✔
145
146	void CUDAParallelizeNestedMap::to_json(nlohmann::json& j) const {	1✔
147	j["transformation_type"] = this->name();	1✔
148	j["parameters"] = nlohmann::json::object();	1✔
149	j["parameters"]["block_size"] = block_size_;	1✔
150
151	serializer::JSONSerializer ser_flat(false);	1✔
152	j["subgraph"] = nlohmann::json::object();	1✔
153	j["subgraph"]["0"] = nlohmann::json::object();	1✔
154	ser_flat.serialize_node(j["subgraph"]["0"], loop_);	1✔
155	}	1✔
156
157	CUDAParallelizeNestedMap CUDAParallelizeNestedMap::
158	from_json(builder::StructuredSDFGBuilder& builder, const nlohmann::json& j) {	1✔
159	// Prefer the embedding-compatible representation (subgraph/parameters),
160	// but fall back to legacy fields (loop/block_size) if needed.
161	const auto& subgraph = j.at("subgraph");	1✔
162	const auto& node_desc = subgraph.at("0");	1✔
163	size_t loop_id = node_desc.at("element_id").get<size_t>();	1✔
164
165	size_t block_size = j.at("parameters").at("block_size").get<size_t>();	1✔
166	auto loop = dynamic_cast<structured_control_flow::StructuredLoop*>(builder.find_element_by_id(loop_id));	1✔
167	if (!loop) {	1✔
168	throw InvalidTransformationDescriptionException("Element with ID " + std::to_string(loop_id) + " is not a loop.");	×
169	}	×
170	return CUDAParallelizeNestedMap(*loop, block_size);	1✔
171	}	1✔
172
173	} // namespace transformations
174	} // namespace sdfg

daisytuner / docc / 31009380971

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous