Přepis řeči - A METHODOLOGY BASED ON TRANSPORTATION PROBLEM MODELING FOR DESIGNING PARALLEL INTERLEAVER ARCHITECTURES

0:00:14	first of a thank you for your coming uh
0:00:17	just like is done in in this the bug done suit fronts look you know
0:00:21	and with that of my supervisor sleep could see
0:00:24	a a C shot mind think my oh
0:00:27	and this presentation i
0:00:29	uh are present that you were technique
0:00:32	a a for mapping that i now
0:00:35	in memory based architecture
0:00:37	and application we have been utilising to uh but in iraq i interleaver architecture which is normally used in
0:00:43	i a coding
0:00:44	a you your where you have a four parts first we present up our problem and then we model our
0:00:48	problem
0:00:50	and next we prepare but a good on that how
0:00:52	uh we saw can free memory mapping
0:00:55	and it last we conclude our presentation uh
0:00:57	uh with the feature perspective
0:01:00	so first just problem formulation and uh first we describe a application and which we apply yeah about the
0:01:05	a a a good time it's that that codes
0:01:08	and which is i perform us uh uh of our uh uh but correction codes uh uh with the forty
0:01:12	characteristics first of all that but uh
0:01:15	but from is uh very close to the capacity of channels and second in
0:01:19	and the use i did you decoding to approximate date
0:01:23	so what is the problem with that date of decoding that we have to uh process data are more than
0:01:27	one time so
0:01:29	but i that eight applications it is very slow and it to improve the
0:01:33	uh to put
0:01:34	we need a better or or decoder architecture in which we have more than and processing elements and
0:01:39	it the do we have a number of memory bank
0:01:41	and then we haven't interconnection connection at five big be in processing elements and memory banks to connect processes that
0:01:46	memory
0:01:47	is architecture is good if uh uh uh at each time instance all a processing demons
0:01:53	i with access different memory banks
0:01:55	but what happens if uh more than and processing much faster access
0:02:00	and the same memory bank
0:02:02	at the same time instance
0:02:04	in that case
0:02:05	um
0:02:06	can problem course and due to this can problem uh a but tense east
0:02:12	and uh uh
0:02:13	assume that you we need a first so we also and use a hardware cost
0:02:17	and a to put has been used
0:02:19	so in this uh are talk will we present a technique to remove these uh and fit problem
0:02:24	for memory based architecture
0:02:27	so first we a from your our problem to they but we have a a you that tally men send
0:02:31	people people single email
0:02:33	and similarly that you we have a point um but all for a main memory banks
0:02:38	yeah
0:02:39	and simply lady where you have a T time instances in which uh process it's font process is that you
0:02:44	men's first in natural order and then interleaved order
0:02:47	which is the requirement for that of would be a
0:02:50	so what is a uh a problem the problems can simple we want to store that men in memory in
0:02:56	such a manner that that each time instant
0:02:58	a all the process as X is uh data in the memory banks without any can
0:03:04	so i that's a model example that we have been prepared
0:03:06	and use in these uh oh
0:03:09	and we have at work that alley men seem that you reality processing meant
0:03:13	and uh also we have a a a time instance is for for natural or out and for for to
0:03:18	go to
0:03:19	in which we processed assessed our data
0:03:22	so first we give you what is that additional approach
0:03:24	to solve this problem that they use an up what used to but a can fit excess get off in
0:03:28	which all the that elements at be presented by a or
0:03:32	and then we can the no was which we need to excess in better for example at you when we
0:03:36	need to excess uh as zero forty it's so
0:03:39	and we can and these nodes to the edges
0:03:42	so idiot a two we need one five and nine so we can have these uh north so the use
0:03:46	and seem we continue and we prepare a what to comfort excess get off
0:03:51	so after the application of what off we yeah
0:03:54	use an node the colouring problem
0:03:57	in the nodes which have been connected to the same image has been giving the different colour
0:04:01	but uh but is a problem the problem that the note culling is then P complete so we do not
0:04:06	of any L go time to find minimum note can
0:04:09	and if we have some of uh you stick this of goals are stick can not find a minimum note
0:04:13	coding so we can find a a minimum
0:04:15	memory banks say we need to uh to be memory men's
0:04:19	but uh if we use note coding approach it is not always possible to find a a a a a
0:04:24	a team memory meant
0:04:25	at the problem that the not coding it the able to find a architecture do and in memory mapping for
0:04:30	example we have a some uh a specific interconnection network and we want to map power data
0:04:35	using the these interconnection networks so
0:04:38	he's the sticks on able to find these type of approach
0:04:42	so we and attack of this proposal by put of um by introducing a transportation problem modeling of or
0:04:49	problem
0:04:51	and uh using this technique we can uh find out a architecture granted memory mapping if interleavers law allowed to
0:04:57	find that
0:04:59	so yeah memory can first one is it to to the conflict the of is quite normal that that to
0:05:04	each time instance all the memory men that memory ben sorry presented with the colours too
0:05:08	all the memory ben should be different
0:05:10	and uh a second one is uh
0:05:13	that the
0:05:14	these that that should be map been one and only one memory bank here the board in natural into the
0:05:18	order you should be all in the same memory men
0:05:21	yeah is there so it all is
0:05:22	all they always in that at memory bank
0:05:25	at in the with order metrics
0:05:27	so now we talk about one morning
0:05:29	so how we prepare a but by part go off a we paper our by but at a graph on
0:05:33	which on one are as we have all the time instance on of size we have all that that north
0:05:37	and we can that time instances is with that that no was at we need to
0:05:41	at which we need to process this that elements for example at T one
0:05:44	we need you of for that so we can at these you for that with a time instance a
0:05:49	or time not be one
0:05:50	in that that we can't any and we we connect all that that don't nodes we a about
0:05:54	uh time instances for natural order
0:05:57	similarly that you we continue and we can at the to one and eleven
0:06:00	uh uh the uh
0:06:02	uh uh that i time instance T five
0:06:05	and uh
0:06:07	a the
0:06:07	i i in that that we construct a but
0:06:10	the will bite but i'd go off
0:06:11	so the are some definitions and false for definition is that the with the semi two factor is
0:06:16	is a
0:06:17	to regular off at to why but this is there of i is equal to the number of time but
0:06:20	this is
0:06:22	and uh at each you know what we have been is uh in a uh is it exactly two edges
0:06:26	here you can see that
0:06:28	all the nodes uh are in to do with two which is which is been to that the board lines
0:06:31	here and here
0:06:33	and all that time nodes have been included in this
0:06:36	and sub off
0:06:38	so this is are
0:06:40	to what on model only there at the if we have a
0:06:43	and D two K or two Q plus fun at each time instant
0:06:46	then we have a K number of this and semi two factors here you can see it and for example
0:06:51	these in this example
0:06:52	uh
0:06:54	we have a digity to so which means that we have of one
0:06:57	and a semi two factor
0:06:59	so using this sort go terms and uh this do the proofs are to in the paper so you can
0:07:03	find these proves in in the paper
0:07:06	so not we can about about the will by part at their off uh into the task problem or in
0:07:11	so we can find a conflict free memory mapping
0:07:14	that's prediction problem is quite simple uh we have a a just like a bite but at that off you
0:07:18	only a one once we have produce a
0:07:20	and side we have a consumers
0:07:22	and it seems that it is that a presentation of metrics on on each it was we have a
0:07:27	uh port use an each on we have a a consumers
0:07:30	so the are some other variables first one is the capacity of to produce and consume but yeah it you
0:07:35	we can put the cap to in front of the
0:07:37	and port you site and are we
0:07:39	a put the
0:07:40	and kept gap is T of the consumer in front of it
0:07:43	so also we have a two
0:07:45	um between the
0:08:00	so we have a would between uh
0:08:02	and pose uh can produce or and consumers uh
0:08:06	and also we have a a a at forty each would we have a cup T of that would and
0:08:10	also cost to put a support each men
0:08:12	of this root for example at you can see that uh
0:08:15	poured use a one is a can i have a would between and consumer but M one and you do
0:08:19	and also we have us some but a variables X X one which is a
0:08:23	a press of that would do all one one you which is a a cost to a support when D
0:08:27	meant on this rule
0:08:28	in that if we prepare a or the task quotation matt takes and put all the values a
0:08:32	now we can what a but that there will by but i to get off on these transportation metric
0:08:37	we put the values Z R zero is uh all that that don't know that an all the
0:08:42	time note that consumers
0:08:43	so we have for the zero is connected with T one and T six a week in give the values
0:08:49	uh
0:08:49	in the cell which is in front of T one zero and a T six zero
0:08:53	but now we have some of the optimisation for a hard the the for of a conflict free memory mapping
0:08:58	or hardware architecture first one it's
0:09:00	at each time instance we can uh X has only one that that so we get better
0:09:04	keep track of S T able to one
0:09:06	because a we have a a a a a that you meant that each time instant
0:09:11	similarly is since we are not concede in the cost of interconnection networks so we can keep the the cost
0:09:16	value you one
0:09:17	and for all that too
0:09:19	image is we continue that that uh put putting said when we you have a connection to T two T
0:09:23	five so we put that values
0:09:25	in front of these uh uh consumers
0:09:28	in that the we continue and compute of their off
0:09:31	also also the are that a variable which is important uh uh is a name of the process sort of
0:09:36	each excess that that that must at that time instant
0:09:39	uh a a but before the uh
0:09:41	and since we are finding a semi two factors so all the
0:09:44	and yeah
0:09:46	supply of all the producers and uh the amount of all the "'cause" you must have been giving a value
0:09:50	too because uh we are can see be baiting a semi two factor
0:09:55	now uh for uh architecture ended mapping we put a name of the process as also
0:10:01	because we need just process of for example they are the do you need to a process that process of
0:10:05	P once so we give the value P one
0:10:07	in front uh in the a do we just got to be D one and zero
0:10:11	that that if we put all the processes and we
0:10:14	all these metrics model of mapping problem it's all the
0:10:17	and cost and uh get best of the was a T we move these man and only the process name
0:10:22	would be knee in in this
0:10:24	medics
0:10:25	so now we continue and would well
0:10:27	a well go time got them is quite simple first we find a cycle
0:10:30	if the cycle is completed at at steps we check but that just completed or not
0:10:34	we find a semi two factor and then remove the semi two factor and are
0:10:38	uh
0:10:41	and then we find as case case semi two factors if it if the just find then yes
0:10:46	that what them is completed if not then we can at each step we can go back out i at
0:10:50	of computer of a algorithm
0:10:52	so is to a some don't to target the at track is but if there so we give a gift
0:10:56	first group um emily bank be note
0:10:59	and uh
0:11:00	after the giving the memory bank we can reduce the capacity of both producers and consumers here the since one
0:11:07	and then be bank is at a good to to the capacity of the mm a board the put a
0:11:11	second the consumer have been reduced by one
0:11:14	no we continue and we give a second
0:11:16	mm memory band to the process of just next because we are constructing a a better of the looks so
0:11:21	the next was that so
0:11:22	P to so we give "'em" emily been be one to this process a
0:11:26	so now the the uh get T of the um
0:11:30	um put a consumers one has been complete so we can remove all the is uh
0:11:35	uh produce of which have been a connected with this uh consumer
0:11:38	so it have been a move from these from the current semi two factor
0:11:42	simulated to sec in to don't had been assigned a similar to the mm memory bank
0:11:47	which connected with for you know order to follow the second constraint that uh each data limit should be mapping
0:11:53	in and only one memory bank
0:11:55	now the capacity of the body of uh for is also completed
0:11:58	in that we now we have to again have to follow the but that a rule
0:12:04	the so be one have been a look at did uh a a uh one have been a look at
0:12:07	you to um emily bank to one so now for the next to
0:12:11	and but it's you've dark a mapping
0:12:14	the next process uh a uh the probably process of which is before the P even has been a good
0:12:18	deed a memory bank be not
0:12:21	uh but this cycle is not complete just T uh here you can see that the process of which is
0:12:25	before the P even has a
0:12:27	we just P T
0:12:28	so we gonna sign up P to D a memory bank be not
0:12:32	in that they seem the yeah
0:12:34	now the a a D model of uh
0:12:37	boating sir seven is complete so we can remove the that produces that have been connected with this
0:12:41	and uh consumer
0:12:43	and in that if we have been continue had you can say that P two is no can net uh
0:12:47	a signed with be know so the next process so
0:12:50	B to you have been assigned a memory bank B even
0:12:53	and uh again the up is um the monte is from phil so we can remove the other
0:12:58	put the saying that if we continue and the we apply a well go time
0:13:03	and until the cycle is completed D you can see that the and cycle is completed because uh these no
0:13:09	buddy set a consumer with the value of one
0:13:12	in a have the
0:13:13	matter
0:13:14	but with that you can see that there's likely is not computed because uh some producers
0:13:18	a you on is left but we fulfilled
0:13:21	so we can uh uh a uh guy you go back and
0:13:25	is uh construct on that the cycle
0:13:27	a a you can and for constructing another the cycle we used a a a a a a yeah
0:13:32	produce says of have been already and deleted it for example are you can see there seven to you did
0:13:37	and is connected T four
0:13:39	so using this seven we can now a look at a a memory bank to well but
0:13:43	process
0:13:45	from the at you can see that the
0:13:47	a a seven
0:13:49	B one in the are um or do T six
0:13:52	yeah
0:13:54	oh next to the P one with this P to has a memory bank of location be note
0:13:58	which means that the P to D which is next to P node in the old use seven must be
0:14:03	the same in banks so here
0:14:05	this uh P to you must be a same memory bank which is be what
0:14:10	and now we can uh you'd use the one car get best steel both producers and
0:14:14	"'cause" you might by one in that to we continue and we
0:14:17	yeah construct our second cycle
0:14:20	after that can section you can see that
0:14:22	the uh model for although um consumers have been fulfilled so which means there this i a vector that being
0:14:28	complete it so we can remove this semi two factor and uh
0:14:32	and now you can see that only one route disconnected with all the producers and consumers which means that we
0:14:37	need only third memory band
0:14:38	to look with to all the two
0:14:41	in that way we have been a well go to is completed
0:14:44	and uh now we find this memory mapping
0:14:48	now we can transform a and here you can the six says a
0:14:52	memory bank B B one so we can put six in the be even
0:14:56	say at is the representation so you can see the relative to architecture
0:15:00	you can see that the gain is a is after uh a that's so in at every time instance
0:15:07	and use is all these uh after the data memory event
0:15:12	so the so so now for the conclusion we we solve a computationally hard mean mapping problem and uh
0:15:19	also also we propose a transportation problem modeling to file architecture don't and memory mapping
0:15:24	and for pitch of perspective we keep the cost to a at each ut once so now we want to
0:15:29	lose the complexity of a dictation but we want to give some value you to these rules
0:15:33	so that's uh we can do the complexity and also we want to extend this a some to other interconnection
0:15:38	networks
0:15:39	and such as that the uh you re
0:15:43	a since we have a king on high level sent is is we want we are currently to developing a
0:15:46	to uh which such as is the construction of memory based architecture is and we generate to
0:15:52	and a conflict free memory mapping and also and technician architecture
0:15:56	and thanks for your question
0:15:59	thank you for attention
0:16:07	pretty quest
0:16:20	okay

A METHODOLOGY BASED ON TRANSPORTATION PROBLEM MODELING FOR DESIGNING PARALLEL INTERLEAVER ARCHITECTURES

Parallel Software Implementation of DSP Algorithms

Přednášející: Awais Hussain Sani, Autoři: Awais Hussain Sani, Philippe Coussy, Cyrille Chavet, Eric Martin, Université de Bretagne Sud / Lab-STICC, France