#include <sdc_scheduling.hpp>

Inheritance diagram for SDCScheduling:

[legend]

Collaboration diagram for SDCScheduling:

[legend]

Public Member Functions
	SDCScheduling (const ParameterConstRef parameters, const HLS_managerRef HLSMgr, unsigned int function_id, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization)
	Constructor. More...

	~SDCScheduling () override
	Destructor. More...

bool	HasToBeExecuted () const override
	Check if this step has actually to be executed. More...

DesignFlowStep_Status	InternalExec () override
	Execute the step. More...

Public Member Functions inherited from Scheduling
	Scheduling (const ParameterConstRef Param, const HLS_managerRef HLSMgr, unsigned int funId, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization=HLSFlowStepSpecializationConstRef())
	Constructor. More...

	~Scheduling () override
	Destructor. More...

const CustomUnorderedMap< vertex, bool > &	get_spec () const
	It returns speculation property map. More...

Public Member Functions inherited from HLSFunctionStep
	HLSFunctionStep (const ParameterConstRef Param, const HLS_managerRef HLSMgr, unsigned int funId, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization=HLSFlowStepSpecializationConstRef())
	Constructor. More...

	~HLSFunctionStep () override
	Destructor. More...

std::string	GetSignature () const final
	Return a unified identifier of this design step. More...

std::string	GetName () const final
	Return the name of this design step. More...

DesignFlowStep_Status	Exec () final
	Execute the step. More...

Public Member Functions inherited from HLS_step
	HLS_step (const ParameterConstRef _parameters, const HLS_managerRef HLSMgr, const DesignFlowManagerConstRef design_flow_manager, const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization=HLSFlowStepSpecializationConstRef())
	Constructor. More...

	~HLS_step () override
	Destructor. More...

std::string	GetSignature () const override
	Return a unified identifier of this design step. More...

std::string	GetName () const override
	Return the name of this design step. More...

virtual std::string	GetKindText () const
	Return the name of the type of this frontend flow step. More...

DesignFlowStepFactoryConstRef	CGetDesignFlowStepFactory () const final
	Return the factory to create this type of steps. More...

Public Member Functions inherited from DesignFlowStep
	DesignFlowStep (const DesignFlowManagerConstRef design_flow_manager, const ParameterConstRef parameters)
	Constructor. More...

virtual	~DesignFlowStep ()
	Destructor. More...

DesignFlowStep_Status	GetStatus () const
	Return the status of this design step. More...

virtual void	WriteDot (std::ostream &out) const
	Write the label for a dot graph. More...

bool	IsComposed () const
	Returns if this step is composed. More...

int	CGetDebugLevel () const
	Return the debug level of the step. More...

virtual void	PrintInitialIR () const
	Dump the initial intermediate representation. More...

virtual void	PrintFinalIR () const
	Dump the final intermediate representation. More...

Data Fields
std::list< std::vector< unsigned int > >	movements_list
	Result of SPECULATIVE_LOOP: the list of movement to be performed (first element is the operation, second element is the old basic block, third element is the new basic block) Movements have to be performed in order. More...

Private Member Functions
void	ExecLoop ()
	Execute the SDCScheduling_Algorithm::SPECULATIVE_LOOP version of the algorithm. More...

void	Initialize () override
	Initialize the step. More...

void	AddDelayConstraints (const meilp_solverRef solver, const OpGraphConstRef filtered_op_graph, const OpGraphConstRef debug_filtered_op_graph, const std::set< vertex, bb_vertex_order_by_map > &loop_bbs)
	Add constraints to force execution in different steps of operations which cannot be chained. More...

void	AddDependenceConstraint (const meilp_solverRef solver, const vertex source, const vertex target, const bool simultaneous) const
	Add constraints to force consecutive execution of dependent operations. More...

void	AddStageConstraints (const meilp_solverRef solver, const vertex operation) const
	Add constraints to force consecutive execution of different pipeline stages. More...

const CustomUnorderedSet< std::tuple< HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship > >	ComputeHLSRelationships (const DesignFlowStep::RelationshipType relationship_type) const override
	Compute the relationship of this step. More...

void	ComputeRelationships (DesignFlowStepSet &relationship, const DesignFlowStep::RelationshipType relationship_type) override
	Compute the relationships of a step with other steps. More...

Private Attributes
OpGraphConstRef	op_graph
	The operation graph used to perform scheduling. More...

BBGraphConstRef	basic_block_graph
	The basic block cfg graph. More...

OpGraphConstRef	feedback_op_graph
	The operation graph with feedback used to perform scheduling. More...

BehavioralHelperConstRef	behavioral_helper
	The behavioral helper. More...

AllocationInformationConstRef	allocation_information
	The allocation. More...

fu_bindingRef	res_binding
	The binding. More...

double	clock_period
	The clock period. More...

double	margin
	The margin which has to be introduced with respect to clock period. More...

CustomUnorderedMap< std::pair< vertex, unsigned int >, unsigned int >	operation_to_varindex
	Map operation-stage to variable index. More...

CustomUnorderedMap< unsigned int, CustomSet< vertex > >	sharing_operations
	The set of unbounded operations. More...

CustomUnorderedSet< unsigned int >	limited_resources
	Set of reachable operations (in scheduling graph) More...

CustomUnorderedSet< EdgeDescriptor >	temp_edges
	The set of temporary flow edges added to the op_graph. More...

Additional Inherited Members
Public Types inherited from DesignFlowStep
enum	RelationshipType { DEPENDENCE_RELATIONSHIP, INVALIDATION_RELATIONSHIP, PRECEDENCE_RELATIONSHIP }
	The relationship type. More...

Static Public Member Functions inherited from HLSFunctionStep
static std::string	ComputeSignature (const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization, const unsigned int function_id)
	Compute the signature of a hls flow step. More...

Static Public Member Functions inherited from HLS_step
static std::string	EnumToName (const HLSFlowStep_Type hls_flow_step_type)
	Given a HLS flow step type, return the name of the type. More...

static const std::string	ComputeSignature (const HLSFlowStep_Type hls_flow_step_type, const HLSFlowStepSpecializationConstRef hls_flow_step_specialization)
	Compute the signature of a hls flow step. More...

Protected Attributes inherited from Scheduling
CustomUnorderedMap< vertex, bool >	spec
	Map for speculation property of each operation vertex. More...

const bool	speculation
	flag to check speculation More...

Protected Attributes inherited from HLSFunctionStep
std::map< unsigned int, unsigned int >	last_bb_ver
	last bb version of the called functions More...

std::map< unsigned int, unsigned int >	last_bitvalue_ver
	The version of bit value IR representation on which this step was applied. More...

const unsigned int	funId
	identifier of the function to be processed (0 means that it is a global step) More...

hlsRef	HLS
	HLS data structure of the function to be analyzed. More...

unsigned int	bb_version
	The version of bb intermediate representation on which this step was applied. More...

unsigned int	bitvalue_version
	The version of bitvalue on which this step was applied. More...

unsigned int	memory_version
	The version of memory representation on which this step was applied. More...

Protected Attributes inherited from HLS_step
const HLS_managerRef	HLSMgr
	information about all the HLS synthesis More...

const HLSFlowStep_Type	hls_flow_step_type
	The type of this step. More...

const HLSFlowStepSpecializationConstRef	hls_flow_step_specialization
	The information about specialization. More...

Protected Attributes inherited from DesignFlowStep
bool	composed
	True if this step represents a composition of design flow steps (e.g., a flow); must be set by specialized constructors. More...

const Wrefcount< const DesignFlowManager >	design_flow_manager
	The design flow manager. More...

const ParameterConstRef	parameters
	Set of input parameters. More...

int	debug_level
	The debug level. More...

const int	output_level
	The output level. More...

Static Protected Attributes inherited from HLS_step
static CustomUnorderedMap< std::string, HLSFlowStep_Type >	command_line_name_to_enum
	Map hls step name to enum. More...

Detailed Description

Definition at line 65 of file sdc_scheduling.hpp.

Constructor & Destructor Documentation

◆ SDCScheduling()

SDCScheduling::SDCScheduling	(	const ParameterConstRef	parameters,
		const HLS_managerRef	HLSMgr,
		unsigned int	function_id,
		const DesignFlowManagerConstRef	design_flow_manager,
		const HLSFlowStepSpecializationConstRef	hls_flow_step_specialization
	)

Constructor.

Parameters

parameters	is the set of input parameters
HLSmgr	is the HLS manager
function_id	is the function index of the function
design_flow_manager	is the hls design flow
hls_flow_step_specialization	specifies how specialize this step

Definition at line 209 of file sdc_scheduling.cpp.

References DesignFlowStep::debug_level, GET_CLASS, DesignFlowStep::parameters, and ~SDCScheduling().

Here is the call graph for this function:

◆ ~SDCScheduling()

SDCScheduling::~SDCScheduling ( )

overridedefault

Destructor.

Referenced by SDCScheduling().

Here is the caller graph for this function:

Member Function Documentation

◆ AddDelayConstraints()

void SDCScheduling::AddDelayConstraints	(	const meilp_solverRef	solver,
		const OpGraphConstRef	filtered_op_graph,
		const OpGraphConstRef	debug_filtered_op_graph,
		const std::set< vertex, bb_vertex_order_by_map > &	loop_bbs
	)

private

Add constraints to force execution in different steps of operations which cannot be chained.

Parameters

solver	is the solver to which constraints have to be added
op_graph	is the operation graph
operation	is the first operation to be considered

The asap starting and ending time

Reverse reachability

For each vertex the set of "live" operations; an operation is live if its distance is less than the clock period

For each vertex the operation for which a constraint has to be added

The execution time of the current operation - for the current operation we must consider last stage NOTE:: Chaining after unbound operation is not allowed

Stage period of first cycle of operations with registered inputs is 0

Computing starting time

Operations cannot be chained if the chain is longer than clock period

Another predecessor (source2) has already a constraint with (other), so we can skip this constraint

Definition at line 222 of file sdc_scheduling.cpp.

Referenced by InternalExec().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddDependenceConstraint()

void SDCScheduling::AddDependenceConstraint	(	const meilp_solverRef	solver,
		const vertex	source,
		const vertex	target,
		const bool	simultaneous
	)		const

private

Add constraints to force consecutive execution of dependent operations.

Parameters

solver	is the solver to which constraints have to be added
source	is the first operation
target	is the second operation
simultaneous	tells if the two operations can be executed in the same clock cycle (chained) or not

Definition at line 473 of file sdc_scheduling.cpp.

References allocation_information, DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, GET_NAME, AllocationInformation::GetCycleLatency(), INDENT_DBG_MEX, meilp_solver::L, op_graph, and operation_to_varindex.

Referenced by InternalExec().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddStageConstraints()

void SDCScheduling::AddStageConstraints	(	const meilp_solverRef	solver,
		const vertex	operation
	)		const

private

Add constraints to force consecutive execution of different pipeline stages.

Parameters

solver	is the solver to which constraints have to be added
operation	is the pipelined operation

Definition at line 485 of file sdc_scheduling.cpp.

References allocation_information, meilp_solver::E, GET_NAME, AllocationInformation::GetCycleLatency(), op_graph, operation_to_varindex, and STR.

Referenced by InternalExec().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ComputeHLSRelationships()

const CustomUnorderedSet< std::tuple< HLSFlowStep_Type, HLSFlowStepSpecializationConstRef, HLSFlowStep_Relationship > > SDCScheduling::ComputeHLSRelationships ( const DesignFlowStep::RelationshipType relationship_type ) const

overrideprivatevirtual

Compute the relationship of this step.

Parameters

relationship_type is the type of relationship to be considered

Returns: the steps in relationship with this

Reimplemented from Scheduling.

Definition at line 524 of file sdc_scheduling.cpp.

References ALLOCATION, CALLED_FUNCTIONS, Scheduling::ComputeHLSRelationships(), DesignFlowStep::DEPENDENCE_RELATIONSHIP, DOMINATOR_ALLOCATION, DesignFlowStep::INVALIDATION_RELATIONSHIP, DesignFlowStep::parameters, DesignFlowStep::PRECEDENCE_RELATIONSHIP, SAME_FUNCTION, THROW_UNREACHABLE, and WHOLE_APPLICATION.

Here is the call graph for this function:

◆ ComputeRelationships()

void SDCScheduling::ComputeRelationships	(	DesignFlowStepSet &	relationship,
		const DesignFlowStep::RelationshipType	relationship_type
	)

overrideprivatevirtual

Compute the relationships of a step with other steps.

Parameters

dependencies	is where relationships will be stored
relationship_type	is the type of relationship to be computed

Managed in HLS_step::ComputeRelationships

Reimplemented from HLSFunctionStep.

Definition at line 498 of file sdc_scheduling.cpp.

References HLSFunctionStep::ComputeRelationships(), FunctionFrontendFlowStep::ComputeSignature(), DesignFlowStep::design_flow_manager, HLSFunctionStep::funId, DesignFlowStep::GetStatus(), HLS_step::HLSMgr, DesignFlowStep::INVALIDATION_RELATIONSHIP, Wrefcount< T >::lock(), NULL_VERTEX, and SUCCESS.

Here is the call graph for this function:

◆ ExecLoop()

void SDCScheduling::ExecLoop ( )

private

Execute the SDCScheduling_Algorithm::SPECULATIVE_LOOP version of the algorithm.

◆ HasToBeExecuted()

bool SDCScheduling::HasToBeExecuted ( ) const

overridevirtual

Check if this step has actually to be executed.

Returns: true if the step has to be executed

Reimplemented from HLSFunctionStep.

Definition at line 562 of file sdc_scheduling.cpp.

References HLSFunctionStep::bb_version, and HLSFunctionStep::HasToBeExecuted().

Here is the call graph for this function:

◆ Initialize()

void SDCScheduling::Initialize ( )

overrideprivatevirtual

Initialize the step.

Build the full reachability map

For the limited resource, the operations assigned to it

If number of resources is limited but larger than number of operations

Removing not actually limited resources

Reimplemented from Scheduling.

Definition at line 1617 of file sdc_scheduling.cpp.

References allocation_information, hls::allocation_information, basic_block_graph, FunctionBehavior::BB, behavioral_helper, FunctionBehavior::CGetBBGraph(), BBGraph::CGetBBNodeInfo(), FunctionBehavior::CGetBehavioralHelper(), FunctionBehavior::CGetOpGraph(), clock_period, DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, feedback_op_graph, FunctionBehavior::FFLSAODG, FunctionBehavior::FLSAODG, HLSFunctionStep::funId, AllocationInformation::get_fu_name(), GET_NAME, AllocationInformation::get_number_fu(), AllocationInformation::get_number_fu_types(), AllocationInformation::GetClockPeriodMargin(), AllocationInformation::GetFuType(), HLSFunctionStep::HLS, hls::HLS_C, HLS_step::HLSMgr, INDENT_DBG_MEX, Scheduling::Initialize(), limited_resources, margin, op_graph, hls::operations, res_binding, hls::Rfu, sharing_operations, STR, and U.

Here is the call graph for this function:

◆ InternalExec()

DesignFlowStep_Status SDCScheduling::InternalExec ( )

overridevirtual

Execute the step.

Returns: the exit status of this step

Vertices not yet added to any tree

FIXME: for the moment the considered graph contains control dependence edges

Create the solver

Compute variables Map real operation-stage to variable index

Create the variables representing the ending of a path Map tree leaf to variable index

next_var_index has been incremented but the + 1 is the makespan

Set integer variables and lower bound

Add consecutive stages constraints

Add dependence constraints: target can start in the same clock cycle in which source ends

Not control dependence

Non speculable operation

Add timing constraints: target can start in the same clock cycle in which source ends only with chaining

For each basic block, the set of unbounded operations found on the paths to it

For each basic block, the set of pipelined operations found on the paths to it

For each basic block, for each functional unit fu, the list of the last n operations executed (n is the number of resource of type fu) - Value is a set since there can be different paths reaching current basic block

NOTE: unbounded operation can start during last stage of multi cycle operation

Resource constraints

Adding last operation constraint: return must be executed after all the other operations.

last cannot be scheduleded with unbounded operations

Setting path end to be the real end

Setting objective function

set the binding information

Check which statements have to be moved For each statement the basic blocks above which it cannot be moved. Phi cannot be moved Operations which depend from the phi cannot be moved before the phi and so on

Set of operations which cannot be moved (at the moment) because of dependencies from gimple phi

IF is not a barrier for controlled operations

Loads which do not have resource limitation can be moved but not speculated; speculation should be prevented by control edges

Computing bb barrier starting from bb barrier of predecesso

Update dominator

If the current is in the barrier, do not check for the candidate

Implements HLSFunctionStep.

Definition at line 574 of file sdc_scheduling.cpp.

References AddDelayConstraints(), AddDependenceConstraint(), AddStageConstraints(), ASLAP::ALAP_fast, allocation_information, basic_block_graph, behavioral_helper, fu_binding::bind(), BehavioralHelper::CanBeSpeculated(), CDG_SELECTOR, FunctionBehavior::CGetBBGraph(), BBGraph::CGetBBGraphInfo(), BBGraph::CGetBBNodeInfo(), FunctionBehavior::CGetBehavioralHelper(), FunctionBehavior::CGetLoops(), FunctionBehavior::CGetOpGraph(), OpGraph::CGetOpNodeInfo(), FunctionBehavior::CheckReachability(), meilp_solver::create_solver(), DesignFlowStep::debug_level, DEBUG_LEVEL_VERY_PEDANTIC, DEBUG_SELECTOR, FunctionBehavior::DOM_TREE, graph::ExistsEdge(), FunctionBehavior::FLSAODDG, FunctionBehavior::FLSAODG, HLSFunctionStep::funId, meilp_solver::G, FunctionBehavior::get_bb_map_levels(), Schedule::get_cstep(), AllocationInformation::get_fu_name(), BehavioralHelper::get_function_name(), GET_NAME, AllocationInformation::get_number_fu(), GET_TYPE, AllocationInformation::GetCycleLatency(), AllocationInformation::GetFuType(), tree_helper::GetMangledFunctionName(), graph::GetSelector(), HLSFunctionStep::HLS, hls::HLS_C, HLS_step::HLSMgr, INDENT_DBG_MEX, AllocationInformation::is_operation_bounded(), limited_resources, meilp_solver::min, movements_list, FunctionBehavior::ogc, op_graph, operation_to_varindex, DesignFlowStep::parameters, res_binding, hls::Rsch, Schedule::set_csteps(), Schedule::set_execution(), Schedule::set_execution_end(), Scheduling::speculation, STR, SUCCESS, lenet_tvm::target, temp_edges, THROW_ASSERT, THROW_ERROR, THROW_UNREACHABLE, TYPE_EXTERNAL, TYPE_IF, TYPE_LABEL, TYPE_LAST_OP, TYPE_LOAD, TYPE_MULTIIF, TYPE_PHI, TYPE_RET, TYPE_RW, TYPE_STORE, TYPE_SWITCH, TYPE_VPHI, Schedule::UpdateTime(), and OpGraph::WriteDot().

Here is the call graph for this function:

Field Documentation

◆ allocation_information

AllocationInformationConstRef SDCScheduling::allocation_information

private

The allocation.

Definition at line 80 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), AddDependenceConstraint(), AddStageConstraints(), Initialize(), and InternalExec().

◆ basic_block_graph

BBGraphConstRef SDCScheduling::basic_block_graph

private

The basic block cfg graph.

Definition at line 71 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), Initialize(), and InternalExec().

◆ behavioral_helper

BehavioralHelperConstRef SDCScheduling::behavioral_helper

private

The behavioral helper.

Definition at line 77 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), Initialize(), and InternalExec().

◆ clock_period

double SDCScheduling::clock_period

private

The clock period.

Definition at line 86 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), and Initialize().

◆ feedback_op_graph

OpGraphConstRef SDCScheduling::feedback_op_graph

private

The operation graph with feedback used to perform scheduling.

Definition at line 74 of file sdc_scheduling.hpp.

Referenced by Initialize().

◆ limited_resources

CustomUnorderedSet<unsigned int> SDCScheduling::limited_resources

private

Set of reachable operations (in scheduling graph)

The set of limited resources

Definition at line 104 of file sdc_scheduling.hpp.

Referenced by Initialize(), and InternalExec().

◆ margin

double SDCScheduling::margin

private

The margin which has to be introduced with respect to clock period.

Definition at line 89 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), and Initialize().

◆ movements_list

std::list<std::vector<unsigned int> > SDCScheduling::movements_list

Result of SPECULATIVE_LOOP: the list of movement to be performed (first element is the operation, second element is the old basic block, third element is the new basic block) Movements have to be performed in order.

Definition at line 164 of file sdc_scheduling.hpp.

Referenced by InternalExec().

◆ op_graph

OpGraphConstRef SDCScheduling::op_graph

private

The operation graph used to perform scheduling.

Definition at line 68 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), AddDependenceConstraint(), AddStageConstraints(), Initialize(), and InternalExec().

◆ operation_to_varindex

CustomUnorderedMap<std::pair<vertex, unsigned int>, unsigned int> SDCScheduling::operation_to_varindex

private

Map operation-stage to variable index.

Definition at line 92 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), AddDependenceConstraint(), AddStageConstraints(), and InternalExec().

◆ res_binding

fu_bindingRef SDCScheduling::res_binding

private

The binding.

Definition at line 83 of file sdc_scheduling.hpp.

Referenced by Initialize(), and InternalExec().

◆ sharing_operations

CustomUnorderedMap<unsigned int, CustomSet<vertex> > SDCScheduling::sharing_operations

private

The set of unbounded operations.

For each shared resource, the operations mapped on it

Definition at line 98 of file sdc_scheduling.hpp.

Referenced by Initialize().

◆ temp_edges

CustomUnorderedSet<EdgeDescriptor> SDCScheduling::temp_edges

private

The set of temporary flow edges added to the op_graph.

Definition at line 108 of file sdc_scheduling.hpp.

Referenced by AddDelayConstraints(), and InternalExec().

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

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

Public Member Functions

Data Fields

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SDCScheduling()

◆ ~SDCScheduling()

Member Function Documentation

◆ AddDelayConstraints()

◆ AddDependenceConstraint()

◆ AddStageConstraints()

◆ ComputeHLSRelationships()

◆ ComputeRelationships()

◆ ExecLoop()

◆ HasToBeExecuted()

◆ Initialize()

◆ InternalExec()

Field Documentation

◆ allocation_information

◆ basic_block_graph

◆ behavioral_helper

◆ clock_period

◆ feedback_op_graph

◆ limited_resources

◆ margin

◆ movements_list

◆ op_graph

◆ operation_to_varindex

◆ res_binding

◆ sharing_operations

◆ temp_edges