| 0:00:14 | so good afternoon everyone |
|---|
| 0:00:16 | um this research is a joint effort between ins are N runs |
|---|
| 0:00:21 | and the university of over in in finland |
|---|
| 0:00:25 | so |
|---|
| 0:00:26 | as we all know um we can describe |
|---|
| 0:00:29 | computer programs |
|---|
| 0:00:30 | at different levels of abstraction by using different |
|---|
| 0:00:34 | programming language |
|---|
| 0:00:37 | um that the lower level of abstraction we can use for example as simply |
|---|
| 0:00:43 | and then on the other extreme extremes we have a |
|---|
| 0:00:46 | such languages is thus |
|---|
| 0:00:47 | some functional of is |
|---|
| 0:00:50 | and then in there between some commonly used language which used like see |
|---|
| 0:00:56 | no these and different languages have a |
|---|
| 0:00:59 | different properties |
|---|
| 0:01:01 | if we program mean ask simply |
|---|
| 0:01:03 | generally we think that we get |
|---|
| 0:01:05 | more efficient implementation |
|---|
| 0:01:08 | on the other hand |
|---|
| 0:01:09 | if we go to the other extreme |
|---|
| 0:01:12 | we get a nice features like code reusability |
|---|
| 0:01:16 | we can analyse the designs |
|---|
| 0:01:18 | we can be a very find that our programs are correct |
|---|
| 0:01:22 | and also our productivity and programming probably goes up |
|---|
| 0:01:28 | in this |
|---|
| 0:01:29 | talk |
|---|
| 0:01:30 | we're concentrating on a language called are we seek out |
|---|
| 0:01:34 | which is pretty high level it's |
|---|
| 0:01:36 | definitely about C |
|---|
| 0:01:40 | and this R P C cal is a data flow language |
|---|
| 0:01:44 | which is actually a subset |
|---|
| 0:01:47 | of the cal language that has originally been developed that the U C berkeley |
|---|
| 0:01:53 | R B C cal was recently |
|---|
| 0:01:55 | standardise find that |
|---|
| 0:01:57 | i S O standardisation organization |
|---|
| 0:02:01 | and i will |
|---|
| 0:02:02 | now so you a simple example |
|---|
| 0:02:04 | how the programs look like in our we seek out |
|---|
| 0:02:09 | so |
|---|
| 0:02:10 | this here is in a program that we can imagine |
|---|
| 0:02:13 | it consists of three actors |
|---|
| 0:02:15 | a |
|---|
| 0:02:16 | B and C |
|---|
| 0:02:18 | and as we know in data flow actors are the elements that do would actual the processing |
|---|
| 0:02:25 | now the data between these actors is transmitted over these |
|---|
| 0:02:29 | five for boppers here |
|---|
| 0:02:32 | there are no other connections |
|---|
| 0:02:34 | these connections are be |
|---|
| 0:02:36 | all the ones that exist between |
|---|
| 0:02:38 | actors and enable the communication |
|---|
| 0:02:42 | if we go inside an actor |
|---|
| 0:02:44 | uh we see that |
|---|
| 0:02:46 | these are actually a finite state machines |
|---|
| 0:02:49 | so we have a different states |
|---|
| 0:02:51 | like this |
|---|
| 0:02:51 | skit age here |
|---|
| 0:02:53 | and then we have a state transitions that we call actions |
|---|
| 0:02:58 | and it's these actions that actually |
|---|
| 0:03:01 | do the data processing |
|---|
| 0:03:02 | so that consume data |
|---|
| 0:03:04 | and they produce data |
|---|
| 0:03:09 | the main difference of R V C cal compare to |
|---|
| 0:03:13 | um traditional data flow language use like a D S that was |
|---|
| 0:03:17 | in the previous presentation |
|---|
| 0:03:19 | is that um |
|---|
| 0:03:21 | are we see cal allows |
|---|
| 0:03:22 | conditional execution |
|---|
| 0:03:24 | so we can have a data dependencies in the al gore |
|---|
| 0:03:29 | um |
|---|
| 0:03:30 | on the one side |
|---|
| 0:03:31 | this is quite good |
|---|
| 0:03:33 | because it makes the land which are applicable to a wide a set of applications |
|---|
| 0:03:38 | we can have a data-dependent applications |
|---|
| 0:03:41 | but there's also a now side that the line which is hard to analyse both score |
|---|
| 0:03:47 | programmers and four compile |
|---|
| 0:03:52 | now the topic of this work |
|---|
| 0:03:54 | is that we want to improve the efficiency of the programs |
|---|
| 0:03:58 | that we have described with these are we see cal language |
|---|
| 0:04:04 | as you remember from this picture |
|---|
| 0:04:07 | or are seek is here on the pretty high level of abstraction |
|---|
| 0:04:11 | and what we want to do |
|---|
| 0:04:13 | is to push |
|---|
| 0:04:14 | the efficiency of this language |
|---|
| 0:04:15 | closer to those |
|---|
| 0:04:17 | programs that have been manually rate than for example in C |
|---|
| 0:04:23 | now |
|---|
| 0:04:23 | we want to do this |
|---|
| 0:04:26 | oh sorry |
|---|
| 0:04:27 | um so you know are we seek how um each data flow actor runs really independently |
|---|
| 0:04:34 | basically this is a good thing |
|---|
| 0:04:36 | because it means |
|---|
| 0:04:37 | that we can re use these |
|---|
| 0:04:39 | actors in other programs also |
|---|
| 0:04:44 | but |
|---|
| 0:04:45 | in practice when we look at the complete that application that's read and you know V C cal |
|---|
| 0:04:50 | we actually find out that these actors are |
|---|
| 0:04:53 | really depending on each other |
|---|
| 0:04:55 | and the reason for this is that |
|---|
| 0:04:57 | um and actor need state ah |
|---|
| 0:05:00 | to be able to operate |
|---|
| 0:05:02 | and if there's no data and actor cannot execute |
|---|
| 0:05:06 | on the other hand |
|---|
| 0:05:07 | if the five for buffer is full |
|---|
| 0:05:09 | and actor condo parade either because there's no space for the output data |
|---|
| 0:05:16 | so we try to |
|---|
| 0:05:18 | automatically discover these inter dependencies between actors |
|---|
| 0:05:23 | and with this information optimized the whole program |
|---|
| 0:05:27 | and make it run fast |
|---|
| 0:05:30 | and the approach that we chose here is |
|---|
| 0:05:33 | dynamic dynamic |
|---|
| 0:05:34 | program is |
|---|
| 0:05:35 | which means that we actually observe |
|---|
| 0:05:38 | a running program |
|---|
| 0:05:40 | and based on the information we get from there we can generate the new program which hopefully is more efficient |
|---|
| 0:05:47 | than the original one |
|---|
| 0:05:51 | so now we can go into the details of our method |
|---|
| 0:05:56 | um i told you about this feature of our we seek out that it enables |
|---|
| 0:06:00 | data dependencies |
|---|
| 0:06:02 | and the first step in our method is to |
|---|
| 0:06:05 | find |
|---|
| 0:06:06 | these data dependencies the are we seek help program |
|---|
| 0:06:11 | and we will call these |
|---|
| 0:06:13 | um |
|---|
| 0:06:15 | signals that calls |
|---|
| 0:06:16 | the data dependencies |
|---|
| 0:06:18 | control signals |
|---|
| 0:06:21 | and we have made a detection rule for finding these signals automatically |
|---|
| 0:06:27 | and the rule is like this |
|---|
| 0:06:29 | um if the value of data in coming from the five oh affects the behaviour of an actor |
|---|
| 0:06:35 | and |
|---|
| 0:06:36 | is a control signal |
|---|
| 0:06:39 | because this is a bit harder to grasp so quickly |
|---|
| 0:06:42 | i will show you an example |
|---|
| 0:06:44 | so this here is and are we seek out program |
|---|
| 0:06:48 | we go to each and every actor in this |
|---|
| 0:06:52 | program |
|---|
| 0:06:53 | and we inspect |
|---|
| 0:06:55 | each and every input port |
|---|
| 0:06:57 | of every actor |
|---|
| 0:06:59 | at some point we arrive at this at at their here |
|---|
| 0:07:04 | and the middle input port |
|---|
| 0:07:06 | and we note this |
|---|
| 0:07:07 | that the data that comes to this court |
|---|
| 0:07:10 | actually affects the behaviour of these |
|---|
| 0:07:13 | at actor |
|---|
| 0:07:15 | so |
|---|
| 0:07:17 | we know that they signal here |
|---|
| 0:07:19 | called E type |
|---|
| 0:07:20 | is the control signal |
|---|
| 0:07:25 | so now that we have discovered these control signals |
|---|
| 0:07:29 | we can go on |
|---|
| 0:07:34 | so |
|---|
| 0:07:36 | as we know the control signals we want to express the behaviour of the whole are we see cal network |
|---|
| 0:07:42 | as a function |
|---|
| 0:07:44 | of the data that values |
|---|
| 0:07:45 | that |
|---|
| 0:07:46 | go to these control signals |
|---|
| 0:07:50 | and |
|---|
| 0:07:51 | to be able to do that |
|---|
| 0:07:53 | we have to insert |
|---|
| 0:07:55 | spatial act there is |
|---|
| 0:07:57 | in these are V see cal network |
|---|
| 0:07:59 | we called than token gate |
|---|
| 0:08:04 | so here an example |
|---|
| 0:08:06 | uh suppose we have two act there's a a and B |
|---|
| 0:08:10 | and we have a detected |
|---|
| 0:08:12 | that the C Q know |
|---|
| 0:08:13 | equals five four |
|---|
| 0:08:15 | between then |
|---|
| 0:08:16 | is a control signal |
|---|
| 0:08:19 | with split the signal and in |
|---|
| 0:08:21 | a token gate active or there |
|---|
| 0:08:27 | so now there has been this bus of word |
|---|
| 0:08:30 | strand and that has a here here |
|---|
| 0:08:33 | um a strand |
|---|
| 0:08:34 | we define as a sequence of actor execution or actor invocation |
|---|
| 0:08:41 | and |
|---|
| 0:08:41 | we define it so that each value |
|---|
| 0:08:45 | of of the control signal that passes to this token gate |
|---|
| 0:08:49 | we in the bulk |
|---|
| 0:08:50 | one strand and |
|---|
| 0:08:51 | that this actor invocations sequence |
|---|
| 0:08:54 | at runtime |
|---|
| 0:08:58 | and |
|---|
| 0:08:58 | we can automatically detect |
|---|
| 0:09:01 | these are |
|---|
| 0:09:03 | with |
|---|
| 0:09:03 | the help of this |
|---|
| 0:09:04 | token gate act |
|---|
| 0:09:08 | we do with so |
|---|
| 0:09:09 | um |
|---|
| 0:09:10 | we let one token at that time to this token gate |
|---|
| 0:09:15 | and observe or the value of that token |
|---|
| 0:09:18 | and then we record |
|---|
| 0:09:20 | the set of actors |
|---|
| 0:09:22 | that this so can invoke |
|---|
| 0:09:27 | however unfortunately this is not enough |
|---|
| 0:09:30 | because there's more flexibility and the cal model |
|---|
| 0:09:34 | uh generally these actors can behave in many different ways |
|---|
| 0:09:39 | for one control signal value |
|---|
| 0:09:43 | so we also need to find out all the different actor behave years |
|---|
| 0:09:48 | that can |
|---|
| 0:09:49 | uh take place for one |
|---|
| 0:09:51 | uh token gate value |
|---|
| 0:09:57 | so |
|---|
| 0:09:59 | we observed |
|---|
| 0:10:00 | that the behavior of an are we see cal actor |
|---|
| 0:10:04 | can be fully predict the deed |
|---|
| 0:10:06 | before it actually execute |
|---|
| 0:10:08 | when wind you know know the following properties |
|---|
| 0:10:12 | of an active or |
|---|
| 0:10:14 | we have to know the values of the actors state variable |
|---|
| 0:10:20 | second |
|---|
| 0:10:21 | we have to know how many tokens there are are at the input ports of that factor |
|---|
| 0:10:28 | and we also need to know |
|---|
| 0:10:29 | what the values of those tokens are |
|---|
| 0:10:34 | and |
|---|
| 0:10:35 | and this set of features here |
|---|
| 0:10:37 | we called the signature of the actor |
|---|
| 0:10:41 | and ask we analyzed the operation of the B C cal network |
|---|
| 0:10:47 | we record |
|---|
| 0:10:48 | this |
|---|
| 0:10:49 | C nature of the actor |
|---|
| 0:10:51 | you for we let it to execute |
|---|
| 0:10:56 | and then |
|---|
| 0:10:57 | for every signature |
|---|
| 0:10:58 | we see what happens |
|---|
| 0:11:00 | we record the set of |
|---|
| 0:11:02 | state transitions |
|---|
| 0:11:03 | that happened and |
|---|
| 0:11:04 | in the act |
|---|
| 0:11:08 | finally this is what we get |
|---|
| 0:11:10 | so |
|---|
| 0:11:11 | you know we have a |
|---|
| 0:11:12 | one uh and gate token |
|---|
| 0:11:14 | or one control signal value |
|---|
| 0:11:17 | it is it can have different values like this and here or or in here |
|---|
| 0:11:23 | and each of these values in the boat |
|---|
| 0:11:25 | one strand |
|---|
| 0:11:27 | this is one and |
|---|
| 0:11:29 | this here is the second one and this is that third one |
|---|
| 0:11:32 | and |
|---|
| 0:11:33 | these is trans |
|---|
| 0:11:34 | consist of actor invocations |
|---|
| 0:11:37 | like the first strand here consists of six actor invocations |
|---|
| 0:11:41 | one two three four five C |
|---|
| 0:11:45 | and then in some actors we have a |
|---|
| 0:11:48 | option on different behaviour patterns like this can behave in two different ways |
|---|
| 0:11:54 | and this one can behave in five different weights |
|---|
| 0:11:57 | and we differentiate between these |
|---|
| 0:12:00 | alternative patterns turns |
|---|
| 0:12:02 | based on the signature |
|---|
| 0:12:06 | now that we have all this information |
|---|
| 0:12:09 | we can go to the final phase of code generation |
|---|
| 0:12:12 | where we create |
|---|
| 0:12:14 | um the new program that hopefully is more efficient |
|---|
| 0:12:18 | and the original one |
|---|
| 0:12:23 | so we have a model to the functionality of the application with these |
|---|
| 0:12:27 | gate token values and actor signature |
|---|
| 0:12:32 | so now we generate a C code of course we could also generate other kind of code like |
|---|
| 0:12:39 | pause col or a simply or whatever |
|---|
| 0:12:42 | but we have chosen C |
|---|
| 0:12:44 | and |
|---|
| 0:12:45 | practically we in sir |
|---|
| 0:12:47 | a set of |
|---|
| 0:12:48 | switch statements to these places where we have these |
|---|
| 0:12:52 | uh different gate token mountains or active can each |
|---|
| 0:12:56 | oh we don't have time to go to any example code |
|---|
| 0:13:00 | but um we have to go directly to the |
|---|
| 0:13:03 | results |
|---|
| 0:13:05 | so |
|---|
| 0:13:05 | we test it this uh method with |
|---|
| 0:13:08 | a few versions of an and pick for part two |
|---|
| 0:13:12 | video decoder |
|---|
| 0:13:14 | um these where |
|---|
| 0:13:15 | different implementations of these video decoders and |
|---|
| 0:13:19 | we got |
|---|
| 0:13:20 | um |
|---|
| 0:13:21 | different speed ups for different implementations |
|---|
| 0:13:24 | so |
|---|
| 0:13:26 | some decoders |
|---|
| 0:13:27 | became more than two times faster |
|---|
| 0:13:30 | where on the ones gained all only about fifteen percent of speed |
|---|
| 0:13:38 | so as a conclusion um |
|---|
| 0:13:41 | we have presented a fully automated approach to speed up |
|---|
| 0:13:45 | programs for than in R B C cal |
|---|
| 0:13:49 | and the are average speed was about one point five times |
|---|
| 0:13:54 | um for future work |
|---|
| 0:13:57 | um based on what we have a learned from this |
|---|
| 0:14:00 | uh work |
|---|
| 0:14:01 | we hope that we can create that's static analysis method we which means that |
|---|
| 0:14:07 | we don't beat you |
|---|
| 0:14:08 | each sound mean a running program but we examine |
|---|
| 0:14:12 | the source code of the program |
|---|
| 0:14:14 | and hope to |
|---|
| 0:14:16 | optimize the application to that |
|---|
| 0:14:20 | and another direction of future work is improve in the code generation |
|---|
| 0:14:26 | which should also improve the speed ups we get |
|---|
| 0:14:30 | and finally |
|---|
| 0:14:32 | we can make them in method applicable to a wide set of applications |
|---|
| 0:14:36 | um it by |
|---|
| 0:14:39 | um let's say rewriting writing that |
|---|
| 0:14:41 | method such that we can have |
|---|
| 0:14:43 | more than one token gate in an application |
|---|
| 0:14:46 | the present |
|---|
| 0:14:48 | um |
|---|
| 0:14:49 | method we have it only allows one token gate are application |
|---|
| 0:14:53 | which is a bit twisted D |
|---|
| 0:14:58 | so thanks for your |
|---|
| 0:14:59 | attention |
|---|
| 0:15:06 | a Q are there questions from a yes |
|---|
| 0:15:14 | uh uh i use that it's uh dynamic approach right so you are basically a ink with some |
|---|
| 0:15:20 | that's sample |
|---|
| 0:15:21 | and uh |
|---|
| 0:15:24 | i mean |
|---|
| 0:15:24 | how many past samples did do not or when you on different test sequence |
|---|
| 0:15:28 | uh |
|---|
| 0:15:29 | does it it's to defend of the musicians or or i mean how you deal be we fact |
|---|
| 0:15:34 | that the |
|---|
| 0:15:35 | basically you need to have set college each and uh |
|---|
| 0:15:38 | you have to learn a little |
|---|
| 0:15:39 | examples |
|---|
| 0:15:40 | to to basically optimized to set called that |
|---|
| 0:15:43 | you can now |
|---|
| 0:15:43 | for |
|---|
| 0:15:44 | yeah that that's |
|---|
| 0:15:47 | yes you're completely correct so |
|---|
| 0:15:49 | uh this dynamic or um code down at is means that |
|---|
| 0:15:53 | um |
|---|
| 0:15:54 | the performance of this optimization is dependent on the input data we can also call it the training data |
|---|
| 0:16:01 | uh we used to one uh a low resolution video sequence as the training data |
|---|
| 0:16:08 | and then we test data the functionality and got these numbers |
|---|
| 0:16:12 | by a high resolution |
|---|
| 0:16:13 | well for high resolution sequence |
|---|
| 0:16:16 | not where much longer |
|---|
| 0:16:18 | but of course i mean there can always be situations |
|---|
| 0:16:21 | not your training data that's not contain |
|---|
| 0:16:25 | all the different options that are there and in that case |
|---|
| 0:16:28 | um |
|---|
| 0:16:29 | the decoding might actually fail |
|---|
| 0:16:31 | we have a some um um |
|---|
| 0:16:33 | let's say safety mechanisms against that but |
|---|
| 0:16:36 | that's why this |
|---|
| 0:16:38 | static analysis would be much better |
|---|
| 0:16:45 | i i just one question so you don't attempt to create a co |
|---|
| 0:16:49 | i |
|---|
| 0:16:50 | yeah |
|---|
| 0:16:50 | you're training |
|---|
| 0:16:52 | you have |
|---|
| 0:16:53 | some sense or is there some way to get |
|---|
| 0:16:56 | and |
|---|
| 0:16:57 | and |
|---|
| 0:16:58 | okay |
|---|
| 0:17:00 | and |
|---|
| 0:17:07 | um |
|---|
| 0:17:08 | no at the moment there is no such mechanism |
|---|
| 0:17:12 | um |
|---|
| 0:17:13 | i think if we would implement that we would already go to watch the |
|---|
| 0:17:18 | static code analysis which we |
|---|
| 0:17:21 | intend to to ran any case so i guess that's a clear direction of future work |
|---|
| 0:17:33 | okay |
|---|
| 0:17:33 | uh we thank you |
|---|
| 0:17:36 | i |
|---|