Class managing ALAP and ASAP algorithms. More...

#include <ASLAP.hpp>

Collaboration diagram for ASLAP:

[legend]

Public Types
enum	ALAP_method { ALAP_fast, ALAP_worst_case, ALAP_with_upper, ALAP_with_upper_minus_one, ALAP_with_partial_scheduling }
	Possible type of ALAP method currently implemented. More...

Public Member Functions
	ASLAP (const HLS_managerConstRef hls_manager, const hlsRef HLS, const bool speculation, const CustomUnorderedSet< vertex > &operations, const ParameterConstRef parameters, unsigned int _ctrl_step_multiplier)
	Constructor. More...

	~ASLAP ()=default
	Destructor. More...

void	print (std::ostream &os) const
	Function that prints the class ASLAP. More...

void	compute_ASAP (const ScheduleConstRef partial_schedule=ScheduleConstRef())
	Function that computes the ASAP scheduling of the graph. More...

const ScheduleConstRef	CGetASAP () const
	Returns the ASAP vector of the vertices. More...

ScheduleRef	GetASAP ()

void	compute_ALAP (ALAP_method met, const ScheduleConstRef partial_schedule=ScheduleConstRef(), bool *feasible=nullptr, const ControlStep=ControlStep(0u))
	Function that computes the ALAP scheduling of the graph. More...

const ScheduleConstRef	CGetALAP () const
	Returns the ALAP vector of the vertices. More...

const ScheduleRef	GetALAP ()
	Return the ALAP (modifiable) More...

void	update_ALAP (const ControlStep maxc, bool *feasible=nullptr, const ScheduleConstRef partial_schedule=ScheduleConstRef())
	Update the ALAP by using maxc as upper bound. More...

const OpGraphConstRef	CGetOpGraph () const
	Gets graph. More...

Private Member Functions
void	add_constraints_to_ALAP ()
	Modify the ALAP scheduling taking into account also technology constraints. More...

void	add_constraints_to_ASAP ()
	Modify the ASAP scheduling taking into account also technology constraints. More...

void	compute_ALAP_fast (bool *feasible=nullptr)
	Compute the standard ALAP scheduling with uncontrained resource. More...

void	compute_ALAP_LB ()
	Compute the ALAP scheduling with uncontrained resources and with the minumum execution time. More...

void	compute_ALAP_worst_case ()
	Compute ALAP using list based euristic to identify the total number of control steps. More...

ControlStep	get_min_csteps () const
	This method returns the minimum number of control steps to schedule the graph. More...

ControlStep	get_max_csteps () const
	This method returns the maximum number of control steps induced by the specification and by the technology constraints. More...

ControlStep	GetCycleLatency (const vertex operation, Allocation_MinMax minmax) const
	Return the number of cycles required to execute an operation. More...

Private Attributes
ScheduleRef	ASAP
	Array storing the ASAP values of the nodes in the graph. More...

ScheduleRef	ALAP
	Array storing the ALAP values of the nodes in the graph. More...

ControlStep	min_tot_csteps
	variable storing the minimum number of control steps required to schedule the graph. More...

ControlStep	max_tot_csteps
	variable storing the maximum number of control steps required to schedule the graph. More...

OpGraphConstRef	beh_graph
	the graph to be scheduled More...

std::deque< vertex >	levels
	constant variable storing the reference to the array of vertexes sorted by topological order associated with the SDG(it can be used also for SG). More...

bool	has_branching_blocks
	is true if the beh_graph has at least one branching block More...

const AllocationInformationConstRef	allocation_information
	The allocation data structure. More...

bool	speculation
	speculation More...

const double	clock_period
	The clock period. More...

int	debug_level
	debug level More...

unsigned int	ctrl_step_multiplier
	multiplier used to take into account chaining during asap/alap computation More...

const CustomUnorderedSet< vertex > &	operations
	relevant vertex for the aslap scheduling More...

Friends
std::ostream &	operator<< (std::ostream &os, const ASLAP &s)
	Friend definition of the << operator. More...

Detailed Description

Class managing ALAP and ASAP algorithms.

Definition at line 75 of file ASLAP.hpp.

Member Enumeration Documentation

◆ ALAP_method

enum ASLAP::ALAP_method

Possible type of ALAP method currently implemented.

ALAP_fast compute ALAP with unlimited constraints (O(n)), but max_ctotstep is calculated considering the fastest functional units
ALAP_worst_case compute ALAP assuming only one resource for each type (O(n)).
ALAP_with_upper compute ALAP using partial_schedule to identify the total number of control steps (O(n)).
ALAP_with_upper_minus_one compute ALAP using partial_schedule to identify the total number of control steps minus one (O(n)).
ALAP_with_partial_scheduling compute ALAP using partial_schedule when is possible (O(n)).

Enumerator
ALAP_fast
ALAP_worst_case
ALAP_with_upper
ALAP_with_upper_minus_one
ALAP_with_partial_scheduling

Definition at line 209 of file ASLAP.hpp.

Constructor & Destructor Documentation

◆ ASLAP()

ASLAP::ASLAP	(	const HLS_managerConstRef	hls_manager,
		const hlsRef	HLS,
		const bool	speculation,
		const CustomUnorderedSet< vertex > &	operations,
		const ParameterConstRef	parameters,
		unsigned int	_ctrl_step_multiplier
	)

Constructor.

Parameters

hls_manager	is the HLS manager
HLS	is the whole HLS data structure.
speculation	tells if speculation could be performed
beh_graph	is the graph on which asap and alap is computed.
parameters	is the set of input parameters

Definition at line 85 of file ASLAP.cpp.

References beh_graph, FunctionBehavior::FLSAODG, hls::functionId, GET_TYPE, has_branching_blocks, levels, FunctionBehavior::SG, speculation, TYPE_FOR, TYPE_IF, TYPE_SWITCH, and TYPE_WHILE.

Referenced by get_max_csteps().

Here is the caller graph for this function:

◆ ~ASLAP()

ASLAP::~ASLAP ( )

default

Destructor.

Referenced by get_max_csteps().

Here is the caller graph for this function:

Member Function Documentation

◆ add_constraints_to_ALAP()

void ASLAP::add_constraints_to_ALAP ( )

private

Modify the ALAP scheduling taking into account also technology constraints.

Parameters

ALL	is the allocation manager.

ALAP_nip[i] contains the number of non immediate predecessor of node i with the same type of operation.

ALAP_p[i] contains the number of predecessor of node i with the same type of operation.

Definition at line 331 of file ASLAP.cpp.

References ALAP, allocation_information, beh_graph, OpGraph::CGetOpNodeInfo(), ctrl_step_multiplier, debug_level, DEBUG_LEVEL_VERY_PEDANTIC, Schedule::get_cstep(), GET_NAME, GetCycleLatency(), level, levels, max, max_tot_csteps, MIN, operations, PRINT_DBG_MEX, PRINT_DBG_STRING, R, vertex2obj< data_obj >::resize(), Schedule::set_execution(), STR, and lenet_tvm::target.

Referenced by update_ALAP().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add_constraints_to_ASAP()

void ASLAP::add_constraints_to_ASAP ( )

private

Modify the ASAP scheduling taking into account also technology constraints.

Currently this function does not correcty work when alternative paths are present.

Parameters

ALL	is the allocation manager.

ASAP_nip[i] contains the number of non immediate predecessor of node i with the same type of operation.

ASAP_p[i] contains the number of predecessor of node i with the same type of operation.

Definition at line 190 of file ASLAP.cpp.

References allocation_information, ASAP, beh_graph, OpGraph::CGetOpNodeInfo(), ctrl_step_multiplier, debug_level, DEBUG_LEVEL_VERY_PEDANTIC, Schedule::get_cstep(), GET_NAME, GetCycleLatency(), level, levels, max, MIN, min_tot_csteps, operations, PRINT_DBG_MEX, PRINT_DBG_STRING, vertex2obj< data_obj >::resize(), and Schedule::set_execution().

Referenced by compute_ASAP().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CGetALAP()

const ScheduleConstRef ASLAP::CGetALAP ( ) const

inline

Returns the ALAP vector of the vertices.

Returns: a map containing the ALAP values for each operation vertex

Definition at line 269 of file ASLAP.hpp.

References ALAP.

◆ CGetASAP()

const ScheduleConstRef ASLAP::CGetASAP ( ) const

inline

Returns the ASAP vector of the vertices.

Returns: a map containing the ASAP values for each operation vertex

Definition at line 235 of file ASLAP.hpp.

References ASAP.

◆ CGetOpGraph()

const OpGraphConstRef ASLAP::CGetOpGraph ( ) const

Gets graph.

Definition at line 132 of file ASLAP.cpp.

References beh_graph.

◆ compute_ALAP()

void ASLAP::compute_ALAP	(	ALAP_method	met,
		const ScheduleConstRef	partial_schedule = `ScheduleConstRef()`,
		bool *	feasible = `nullptr`,
		const ControlStep	est_upper_bound = `ControlStep(0u)`
	)

Function that computes the ALAP scheduling of the graph.

Parameters

met	is the method adopted to compute the ALAP scheduling ALAP_fast compute ALAP with unlimited constraints (O(n)), but max_ctotstep is calculated considering the fastest functional units ALAP_worst_case compute ALAP assuming only one resource for each type (O(n)). ALAP_with_upper compute ALAP using partial_schedule to identify the total number of control steps (O(n)). ALAP_with_upper_minus_one compute ALAP using partial_schedule to identify the total number of control steps minus one (O(n)). ALAP_with_partial_scheduling compute ALAP using partial_schedule when is possible (O(n)).
partial_schedule	is a partial schedule that has to be considered
feasible	is where feasibility of calculated ASAP & ALAP will be put; if used it must be setted initially to true
est_upper_bound	is an upper estimation of the control steps (used by ).

Definition at line 420 of file ASLAP.cpp.

References ALAP, ALAP_fast, ALAP_with_partial_scheduling, ALAP_with_upper, ALAP_with_upper_minus_one, ALAP_worst_case, Schedule::clear(), compute_ALAP_worst_case(), debug_level, DEBUG_LEVEL_VERY_PEDANTIC, max_tot_csteps, PRINT_DBG_MEX, Schedule::set_csteps(), THROW_ASSERT, THROW_ERROR, and update_ALAP().

Referenced by GetASAP().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_ALAP_fast()

void ASLAP::compute_ALAP_fast ( bool * feasible = nullptr )

private

Compute the standard ALAP scheduling with uncontrained resource.

Parameters

feasible is where feasibility of calculated ASAP & ALAP will be put; if used it must be setted initially to true

Definition at line 501 of file ASLAP.cpp.

References ALAP, ASAP, beh_graph, ctrl_step_multiplier, debug_level, DEBUG_LEVEL_PEDANTIC, from_strongtype_cast(), Schedule::get_cstep(), GET_NAME, GetCycleLatency(), Schedule::is_scheduled(), level, levels, max_tot_csteps, MIN, PRINT_DBG_MEX, vertex2obj< data_obj >::resize(), Schedule::set_execution(), STR, and lenet_tvm::target.

Referenced by update_ALAP().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_ALAP_LB()

void ASLAP::compute_ALAP_LB ( )

private

Compute the ALAP scheduling with uncontrained resources and with the minumum execution time.

Considering the minimum execution time is possible when it is already computed the max_tot_csteps. The standard ALAP algorithms should use the maximum execution time since it does not know the total number of control steps thus requiring a worst estimation of the ALAP time for each operation.

Parameters

ALL	is the allocation manager.

◆ compute_ALAP_worst_case()

void ASLAP::compute_ALAP_worst_case ( )

private

Compute ALAP using list based euristic to identify the total number of control steps.

Parameters

ALL	is the allocation manager.

Definition at line 545 of file ASLAP.cpp.

References ALAP, allocation_information, beh_graph, ctrl_step_multiplier, Schedule::get_cstep(), GetCycleLatency(), AllocationInformation::initiation_time, level, levels, max, MAX, max_tot_csteps, operations, Schedule::set_execution(), and lenet_tvm::target.

Referenced by compute_ALAP().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_ASAP()

void ASLAP::compute_ASAP ( const ScheduleConstRef partial_schedule = ScheduleConstRef() )

Function that computes the ASAP scheduling of the graph.

Parameters

ALL	is the allocation manager.
partial_schedule	is a partial schedule that has to be taken into account

Definition at line 273 of file ASLAP.cpp.

References add_constraints_to_ASAP(), ASAP, beh_graph, Schedule::clear(), ctrl_step_multiplier, debug_level, DEBUG_LEVEL_PEDANTIC, DEBUG_LEVEL_VERBOSE, from_strongtype_cast(), Schedule::get_cstep(), GET_NAME, GetCycleLatency(), has_branching_blocks, Schedule::is_scheduled(), level, levels, MIN, min_tot_csteps, PRINT_DBG_MEX, vertex2obj< data_obj >::resize(), Schedule::set_csteps(), Schedule::set_execution(), STR, and WITH_CONSTRAINT.

Here is the call graph for this function:

◆ get_max_csteps()

ControlStep ASLAP::get_max_csteps ( ) const

inlineprivate

This method returns the maximum number of control steps induced by the specification and by the technology constraints.

Returns: a worst-case estimation of number of control steps.

Definition at line 166 of file ASLAP.hpp.

References ASLAP(), GetCycleLatency(), max_tot_csteps, test_panda::parameters, and ~ASLAP().

Here is the call graph for this function:

◆ get_min_csteps()

ControlStep ASLAP::get_min_csteps ( ) const

inlineprivate

This method returns the minimum number of control steps to schedule the graph.

Returns: the best-case estimation of control steps.

Definition at line 156 of file ASLAP.hpp.

References min_tot_csteps.

◆ GetALAP()

const ScheduleRef ASLAP::GetALAP ( )

inline

Return the ALAP (modifiable)

Definition at line 277 of file ASLAP.hpp.

References ALAP, and update_ALAP().

Here is the call graph for this function:

◆ GetASAP()

ScheduleRef ASLAP::GetASAP ( )

inline

Definition at line 240 of file ASLAP.hpp.

References ASAP, and compute_ALAP().

Here is the call graph for this function:

◆ GetCycleLatency()

ControlStep ASLAP::GetCycleLatency	(	const vertex	operation,
		Allocation_MinMax	minmax
	)		const

private

Return the number of cycles required to execute an operation.

Parameters

operation	is the operation
minmax	specifies if the minimum or the maximum execution time must be returned

Returns: the number of cycles

Definition at line 601 of file ASLAP.cpp.

References allocation_information, beh_graph, clock_period, ctrl_step_multiplier, debug_level, DEBUG_LEVEL_PEDANTIC, AllocationInformation::execution_time, GET_NAME, PRINT_DBG_MEX, and STR.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), compute_ALAP_fast(), compute_ALAP_worst_case(), compute_ASAP(), and get_max_csteps().

Here is the caller graph for this function:

◆ print()

void ASLAP::print ( std::ostream & os ) const

Function that prints the class ASLAP.

Parameters

os	is the stream where the class has to be printed

Definition at line 137 of file ASLAP.cpp.

References ALAP, ASAP, Schedule::num_scheduled(), and Schedule::print().

Here is the call graph for this function:

◆ update_ALAP()

void ASLAP::update_ALAP	(	const ControlStep	maxc,
		bool *	feasible = `nullptr`,
		const ScheduleConstRef	partial_schedule = `ScheduleConstRef()`
	)

Update the ALAP by using maxc as upper bound.

This method modifies the maximum number of control steps and updates the ALAP scheduling if it possible.

Parameters

maxc	is the maximum value of the control steps.
feasible	is where feasibility of calculated ASAP & ALAP will be put; if used it must be setted initially to true
partial_schedule	is a partial schedule that has to be taken into account

Definition at line 475 of file ASLAP.cpp.

References add_constraints_to_ALAP(), ALAP, Schedule::clear(), compute_ALAP_fast(), debug_level, DEBUG_LEVEL_PEDANTIC, has_branching_blocks, level, levels, max_tot_csteps, PRINT_DBG_MEX, Schedule::set_execution(), and WITH_CONSTRAINT.

Referenced by compute_ALAP(), and GetALAP().

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<<	(	std::ostream &	os,
		const ASLAP &	s
	)

friend

Friend definition of the << operator.

Definition at line 296 of file ASLAP.hpp.

Field Documentation

◆ ALAP

ScheduleRef ASLAP::ALAP

private

Array storing the ALAP values of the nodes in the graph.

Definition at line 82 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), CGetALAP(), compute_ALAP(), compute_ALAP_fast(), compute_ALAP_worst_case(), GetALAP(), print(), and update_ALAP().

◆ allocation_information

const AllocationInformationConstRef ASLAP::allocation_information

private

The allocation data structure.

Definition at line 101 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), compute_ALAP_worst_case(), and GetCycleLatency().

◆ ASAP

ScheduleRef ASLAP::ASAP

private

Array storing the ASAP values of the nodes in the graph.

Definition at line 79 of file ASLAP.hpp.

Referenced by add_constraints_to_ASAP(), CGetASAP(), compute_ALAP_fast(), compute_ASAP(), GetASAP(), and print().

◆ beh_graph

OpGraphConstRef ASLAP::beh_graph

private

the graph to be scheduled

Definition at line 91 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), ASLAP(), CGetOpGraph(), compute_ALAP_fast(), compute_ALAP_worst_case(), compute_ASAP(), and GetCycleLatency().

◆ clock_period

const double ASLAP::clock_period

private

The clock period.

Definition at line 107 of file ASLAP.hpp.

Referenced by GetCycleLatency().

◆ ctrl_step_multiplier

unsigned int ASLAP::ctrl_step_multiplier

private

multiplier used to take into account chaining during asap/alap computation

Definition at line 113 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), compute_ALAP_fast(), compute_ALAP_worst_case(), compute_ASAP(), and GetCycleLatency().

◆ debug_level

int ASLAP::debug_level

private

debug level

Definition at line 110 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), compute_ALAP(), compute_ALAP_fast(), compute_ASAP(), GetCycleLatency(), and update_ALAP().

◆ has_branching_blocks

bool ASLAP::has_branching_blocks

private

is true if the beh_graph has at least one branching block

Definition at line 98 of file ASLAP.hpp.

Referenced by ASLAP(), compute_ASAP(), and update_ALAP().

◆ levels

std::deque<vertex> ASLAP::levels

private

constant variable storing the reference to the array of vertexes sorted by topological order associated with the SDG(it can be used also for SG).

Definition at line 95 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), ASLAP(), compute_ALAP_fast(), compute_ALAP_worst_case(), compute_ASAP(), and update_ALAP().

◆ max_tot_csteps

ControlStep ASLAP::max_tot_csteps

private

variable storing the maximum number of control steps required to schedule the graph.

Definition at line 88 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), compute_ALAP(), compute_ALAP_fast(), compute_ALAP_worst_case(), get_max_csteps(), and update_ALAP().

◆ min_tot_csteps

ControlStep ASLAP::min_tot_csteps

private

variable storing the minimum number of control steps required to schedule the graph.

Definition at line 85 of file ASLAP.hpp.

Referenced by add_constraints_to_ASAP(), compute_ASAP(), and get_min_csteps().

◆ operations

const CustomUnorderedSet<vertex>& ASLAP::operations

private

relevant vertex for the aslap scheduling

Definition at line 116 of file ASLAP.hpp.

Referenced by add_constraints_to_ALAP(), add_constraints_to_ASAP(), and compute_ALAP_worst_case().

◆ speculation

bool ASLAP::speculation

private

speculation

Definition at line 104 of file ASLAP.hpp.

Referenced by ASLAP().

The documentation for this class was generated from the following files:

/workspace/src/HLS/scheduling/ASLAP.hpp
/workspace/src/HLS/scheduling/ASLAP.cpp

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Enumeration Documentation

◆ ALAP_method

Constructor & Destructor Documentation

◆ ASLAP()

◆ ~ASLAP()

Member Function Documentation

◆ add_constraints_to_ALAP()

◆ add_constraints_to_ASAP()

◆ CGetALAP()

◆ CGetASAP()

◆ CGetOpGraph()

◆ compute_ALAP()

◆ compute_ALAP_fast()

◆ compute_ALAP_LB()

◆ compute_ALAP_worst_case()

◆ compute_ASAP()

◆ get_max_csteps()

◆ get_min_csteps()

◆ GetALAP()

◆ GetASAP()

◆ GetCycleLatency()

◆ print()

◆ update_ALAP()

Friends And Related Function Documentation

◆ operator<<

Field Documentation

◆ ALAP

◆ allocation_information

◆ ASAP

◆ beh_graph

◆ clock_period

◆ ctrl_step_multiplier

◆ debug_level

◆ has_branching_blocks

◆ levels

◆ max_tot_csteps

◆ min_tot_csteps

◆ operations

◆ speculation