----------------------------------------------------------------------------------
-- Company: 
-- Engineer: 
-- 
-- Create Date:    16:05:18 03/22/2009 
-- Design Name: 
-- Module Name:    dfg_scheduler - Behavioral 
-- Project Name: 
-- Target Devices: 
-- Tool versions: 
-- Description: 
--
-- Dependencies: 
--
-- Revision: 
-- Revision 0.01 - File Created
-- Additional Comments: 
--
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use IEEE.NUMERIC_STD.ALL;

---- Uncomment the following library declaration if instantiating
---- any Xilinx primitives in this code.
--library UNISIM;
--use UNISIM.VComponents.all;

entity dfg_scheduler is
generic
	(  		
		NUM_ACTIVE_MICROS					 : integer					:= 2;
		NUM_DFG_NODES                  : integer              := 16;
		NULL_NODE							 : integer					:= 16;
		NUM_MICROS                     : integer              := 2;		
		ITER_NUM_WIDTH                 : integer              := 16;
		MAX_ITER								 : integer              := 50;		
		DFG_NODE_WIDTH						 : integer              := 8;
		NUM_STATES							 : integer					:= 6
    
	);
   Port 
	( 
		clk : in STD_LOGIC;
      reset : in STD_LOGIC;
		executing : in STD_LOGIC_VECTOR (NUM_MICROS-1 downto 0);
		iteration_num : out STD_LOGIC_VECTOR ((NUM_MICROS*ITER_NUM_WIDTH)-1 downto 0);      
      start_exec : out STD_LOGIC_VECTOR (NUM_MICROS-1 downto 0);
      dfg_node : out STD_LOGIC_VECTOR ((NUM_MICROS*DFG_NODE_WIDTH)-1 downto 0);
		proc_done : out STD_LOGIC_VECTOR (NUM_MICROS-1 downto 0)
	);           
end dfg_scheduler;

architecture Behavioral of dfg_scheduler is
	type DFG_COUNT_TABLE is array (0 to NUM_DFG_NODES-1) of integer range 0 to MAX_ITER;
	type DFG_DEPEND_MATRIX is array (0 to NUM_DFG_NODES-1, 0 to NUM_DFG_NODES-1) of integer range 0 to NUM_DFG_NODES;
	type SCHEDULE_MATRIX is array (0 to NUM_MICROS-1, 0 to NUM_DFG_NODES-1) of integer range 0 to NUM_DFG_NODES;
	type PIPELINE_TABLE is array (0 to NUM_MICROS-1) of integer range 0 to NUM_DFG_NODES;
	type STATE_TABLE is array (0 to NUM_MICROS-1) of integer range 0 to NUM_STATES;
	
	constant dfg_dependencies : DFG_DEPEND_MATRIX := ( (NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(			0, 		  1, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(		   0,         1,         2, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(        0,         2, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(        3,         4, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(        3,         4,         5, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(        3,         5, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(			6, 		  7, 			 8, 			9, 		 10, 			11, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(		  12, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(		  12, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																		(		  12, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ));
	constant pipeline_schedule : SCHEDULE_MATRIX := ( (         0,        4, 			 5,        10,         8,        11,        14,        15, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ),
																	  ( 			2,        1,          3,         7,         6,         9,        12,        13, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE, NULL_NODE ) );	
	
	
	-- this is the number of times that each node in the dfg has been executed
	signal dfg_counts : DFG_COUNT_TABLE := (others => 0);
	
	signal curr_iteration : integer range 0 to MAX_ITER := 0;
	-- this is the index into the pipeline that each micro is currently at	
	signal pipeline_index : PIPELINE_TABLE := (others => 0);
	-- this is the state in the state machine for each processor
	signal curr_state : STATE_TABLE := (others => 0);   
begin
	schedule_process : process( clk ) is
	variable clear_to_run : STD_LOGIC_VECTOR (NUM_MICROS-1 downto 0) := (others => '1');
	variable min_unfinished_pipeline_index : DFG_COUNT_TABLE := (others => 0);
	
	begin		
		if (clk'event and clk = '1') then
			if (reset = '1') then
				iteration_num <= (others => '0');
				dfg_node <= (others => '0');
				start_exec <= (others => '0');
				curr_iteration <= 0;
				dfg_counts <= (others => 0);
				pipeline_index <= (others => 0);
				curr_state <= (others => 0);
				proc_done <= (others => '0');				
			else
				for i in 0 to NUM_ACTIVE_MICROS-1 loop
					case curr_state(i) is 
						when 0 => -- this is the state when a node in the dfg is not currently running, so we need to check 
								    -- to see if the next node in the pipeline can run
							
							min_unfinished_pipeline_index(i) := NULL_NODE;
							
							-- this for loop is to check which node in the pipeline is the first that can be scheduled
							for k in NUM_DFG_NODES-1 downto 0 loop
								if (pipeline_schedule(i, k) /= NULL_NODE) then
									if (dfg_counts(pipeline_schedule(i, k)) < MAX_ITER) then
										min_unfinished_pipeline_index(i) := k;
									end if;
								end if;
							end loop;
							
							-- if all nodes are finished, then we are done executing
							if (min_unfinished_pipeline_index(i) = NULL_NODE) then
								curr_state(i) <= 4;								
							else
								clear_to_run(i) := '1'; --set the clear_to_run flag to 1
								
								-- check to see if this node has finished all of it's iteratons, if so then clear_to_run = 0
								if (dfg_counts(pipeline_schedule(i, pipeline_index(i))) >= MAX_ITER) then
									clear_to_run(i) := '0';
								end if;								
								
								-- check all the nodes that this node is dependent on, if they are not finished one iteration
								-- higher than the current node then we cannot execute, so clear_to_run = 0
								for j in 0 to NUM_DFG_NODES-1 loop
									if (dfg_dependencies(pipeline_schedule(i, pipeline_index(i)), j) /= NULL_NODE) then
										if (dfg_counts(dfg_dependencies(pipeline_schedule(i, pipeline_index(i)), j)) <= dfg_counts(pipeline_schedule(i, pipeline_index(i)))) then
											clear_to_run(i) := '0';
										end if;									
									end if;								
								end loop;
									
									-- if clear_to_run is 1 then we can start executing the current node									
								if (clear_to_run(i) = '1') then 								
									dfg_node(((i+1)*DFG_NODE_WIDTH)-1 downto i*DFG_NODE_WIDTH) <= STD_LOGIC_VECTOR(to_unsigned(pipeline_schedule(i, pipeline_index(i)), DFG_NODE_WIDTH));
									start_exec(i) <= '1';
									iteration_num(((i+1)*ITER_NUM_WIDTH)-1 downto i*ITER_NUM_WIDTH) <= STD_LOGIC_VECTOR(to_unsigned(dfg_counts(pipeline_schedule(i, pipeline_index(i)))+1, ITER_NUM_WIDTH)); 
									curr_state(i) <= 1; -- go to the next state 
								else 
									--if clear_to_run is 0, then we can't execute the current node, so we should go back to the
									-- beginning of the pipeline schedule and execute the first node that can be executed
									pipeline_index(i) <= min_unfinished_pipeline_index(i);								
								end if;
							end if;
						when 1 => -- this is the state right after a node was told to execute, we will wait here until the micro starts to execute
							if (executing(i) = '1') then -- this is the case where the micro has started executing the assigned node
								start_exec(i) <= '0';
								curr_state(i) <= 2; -- go to the next state 												
							else --this is the case where the micro has not started executing yet
								dfg_node(((i+1)*DFG_NODE_WIDTH)-1 downto i*DFG_NODE_WIDTH) <= STD_LOGIC_VECTOR(to_unsigned(pipeline_schedule(i, pipeline_index(i)), DFG_NODE_WIDTH));
								start_exec(i) <= '1';
								iteration_num(((i+1)*ITER_NUM_WIDTH)-1 downto i*ITER_NUM_WIDTH) <= STD_LOGIC_VECTOR(to_unsigned(dfg_counts(pipeline_schedule(i, pipeline_index(i)))+1, ITER_NUM_WIDTH)); 
							end if;
						when 2 => -- this is the state when we are waiting for the current micro to finish executing its current node
							if (executing(i) = '0') then -- this is the case where the micro has started executing the assigned node
								dfg_counts(pipeline_schedule(i, pipeline_index(i))) <= dfg_counts(pipeline_schedule(i, pipeline_index(i))) + 1;
								curr_state(i) <= 3; -- goto the next state
							end if;
						when 3 => -- this is the state one clock cycle after 
							if ((pipeline_index(i)+1 = NUM_DFG_NODES) or (pipeline_schedule(i, pipeline_index(i)+1) = NULL_NODE)) then
								-- this for loop is to check which node in the pipeline is the first that can be scheduled
								for k in NUM_DFG_NODES-1 downto 0 loop
									if (pipeline_schedule(i, k) /= NULL_NODE) then
										if (dfg_counts(pipeline_schedule(i, k)) < MAX_ITER) then
											min_unfinished_pipeline_index(i) := k;
										end if;
									end if;
								end loop;								
								pipeline_index(i) <= min_unfinished_pipeline_index(i);								
							else
								pipeline_index(i) <= pipeline_index(i) + 1;
							end if;								
								
							curr_state(i) <= 0; -- return to the first state 													
						when 4 =>
							proc_done(i) <= '1'; 
						when others =>
							curr_state(i) <= 0; -- return to the first state 
					end case;
				end loop; 				
			end if;
		end if;
	end process schedule_process;

end Behavioral;

