Software Prefetching using Machine learning

Software Prefetching using Machine learning

[Irfan Ullah (울라 이르판)]

[-- Attachment #1.1: Type: text/plain, Size: 2123 bytes --]

Dear All,
Thanks in advance. I am a PhD candidate, and currently I have started
working on kernel development. My professor told me to implement this paper
<https://arxiv.org/abs/1803.02329>. In this paper authors have used machine
learning to predict the next missed addresses.They used instruction
addresses (program counters PCs), and corresponding missed addresses as
features to train the machine learning classifier.
As  a kernel newbie, I don't know how to initiate the implementation. I am
thinking to implement it in the following steps:
1- Saving instruction addresses (PCs), and corresponding missed addresses
2- Perform the machine learning
3-Do the prediction using machine learning classifier, and swap in/swap out
the pages.

I have some questions that
1) How can I directly store the missed addresses, and instruction addresses
from kernel handle_mm_fault() to a file?
 2) How can I use machine learning classifier in the kernel for predicting
addresses?
3) Is there any way to do the machine learning in the user space in python,
and then transfer  the classifier in bytes forms to the kernel space for
address predictions ?

Currently, I am stuck in getting the missed addresses by storing it into
the file. I am trying to send the missed addresses to the user space from
the kernel space, and store it into the file. I know that /proc, ioctl, and
netlink are some options to exchange data between  kernel and user spaces.
I have selected the netlink, and trying to customize this code
<https://gist.github.com/JeonghunLee/17db624665da91ee46c221b00e2b93f5> for
my task. I need some type of communication API which let me do exchange
anytype of data (integers, string, bytes, and may be structures to bind all
these types of data) between kernel space, and user space.
Any type of help,  and guidelines will be highly appreciated.
Thank you.

-- 
*Best Regards,*


*Mr. Irfan Ullah*
PhD Candidate
Data and Knowledge Engineering(DKE) Lab
Department of Computer Science and Engineering
Kyung Hee University, South Korea.
 +82-010-591-51651 <+82%2010-3877-8867>
  sahibzada.iu@gmail.com
 sahibzada_irfanullah

[-- Attachment #1.2: Type: text/html, Size: 4085 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Greg KH]

On Wed, Oct 09, 2019 at 12:37:51PM +0900, Irfan Ullah (울라 이르판) wrote:
> Dear All,
> Thanks in advance. I am a PhD candidate, and currently I have started
> working on kernel development. My professor told me to implement this paper
> <https://arxiv.org/abs/1803.02329>. In this paper authors have used machine
> learning to predict the next missed addresses.They used instruction
> addresses (program counters PCs), and corresponding missed addresses as
> features to train the machine learning classifier.
> As  a kernel newbie, I don't know how to initiate the implementation. I am
> thinking to implement it in the following steps:
> 1- Saving instruction addresses (PCs), and corresponding missed addresses
> 2- Perform the machine learning
> 3-Do the prediction using machine learning classifier, and swap in/swap out
> the pages.

Are we going to get credit for doing your assignment?  :)

If this is for school, please work on this on your own.  And work with
your professor, perhaps this isn't even possible...

good luck!

greg k-h

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Valdis Klētnieks]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.1: Type: text/plain; charset=utf-8, Size: 2404 bytes --]

On Wed, 09 Oct 2019 12:37:51 +0900, Irfan Ullah said:

> Thanks in advance. I am a PhD candidate, and currently I have started
> working on kernel development. My professor told me to implement this paper
> <https://arxiv.org/abs/1803.02329>. In this paper authors have used machine
> learning to predict the next missed addresses.

From the abstract:

On a suite of challenging benchmark datasets, we find that neural networks
consistently demonstrate superior performance in terms of precision and recall

Delving further into the paper, we discover that the researchers have learned that
if you run Spec CPU2006 enough times, a neural network can learn what memory access
patterns Spec CPU2006 exhibits.

But they don't demonstrate that the patterns learned transfer to any other programs.
And nobody sane runs the exact same program with the exact same inputs repeatedly
unless they're doing benchmarking.

Ah, academia - where novelty of an idea is sufficient to get published, and considerations
of whether it's a *useful* idea are totally disregarded.

> 1) How can I directly store the missed addresses, and instruction addresses
> from kernel handle_mm_fault() to a file?

Don't do that.  Pass the data to userspace via netlink or debugfs or shared
memory or other means, and have userspace handle it.

> 2) How can I use machine learning classifier in the kernel for predicting addresses?    

Well... in general, you won't be able to do much actually *useful*, because of
time scales.  If your predictor says "Oh, program XYZ will need page 1AB83D 20
milliseconds from now", but it takes 10 milliseconds to bring a page in, your
predictor has only 10 milliseconds to make the prediction in order to be
useful.

And in fact, you probably have even less, because your predictor has to be fast
enough and use little enough memory that it doesn't significantly affect CPU,
cache, or RAM usage.

> 3) Is there any way to do the machine learning in the user space in python, and
> then transfer  the classifier in bytes forms to the kernel space for address
> predictions ?

Sure, there's plenty of ways, from using shared memory to creating an ioctl().

But all of them are going to have the same "you need to do it in less time than
it takes for the program you're predicting to reach the point for the prediction".

Good luck, you will need it.

[-- Attachment #1.2: Type: application/pgp-signature, Size: 832 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Ruben Safir]

On 10/9/19 3:08 PM, Valdis Klētnieks wrote:
> Ah, academia - where novelty of an idea is sufficient to get published, and considerations
> of whether it's a *useful* idea are totally disregarded.


like thermal dynamics, relativity, quantum mechanics, paleontology,
biological computational mathematics, and the Turing machine... all of
which fit that description.

There will be AI built into the kernel eventually to do a number of
things, and preventing locks and crashes and preemptive statistical
analysis execution code will without a doubt play a key roll.



-- 
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002

http://www.nylxs.com - Leadership Development in Free Software
http://www.brooklyn-living.com

Being so tracked is for FARM ANIMALS and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Ruben Safir]

On 10/9/19 3:08 PM, Valdis Klētnieks wrote:
> Ah, academia - where novelty of an idea is sufficient to get published, and considerations
> of whether it's a *useful* idea are totally disregarded.


or better, it will be built into systemd!



-- 
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002

http://www.nylxs.com - Leadership Development in Free Software
http://www.brooklyn-living.com

Being so tracked is for FARM ANIMALS and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Irfan Ullah (울라 이르판)]

[-- Attachment #1.1: Type: text/plain, Size: 1886 bytes --]

Thank you  for the responses.
It is not my assignment. Actually, we have initiated a project based on the
idea "incorporating artificial intelligence in the linux kernel to increase
its performance". The basic aim of the project to increase the operating
system's performance utilizing software based artificial intelligence
techniques without using any type of hardware, and then we will  test our
technique on various hardwares, i.e., classic HDD,SSD, NUMA etc. to
observe/compare their performances. We took a start from prefetching using
machine learning.....:)

On Thu, Oct 10, 2019 at 9:26 AM Ruben Safir <ruben@mrbrklyn.com> wrote:

> On 10/9/19 3:08 PM, Valdis Klētnieks wrote:
> > Ah, academia - where novelty of an idea is sufficient to get published,
> and considerations
> > of whether it's a *useful* idea are totally disregarded.
>
>
> or better, it will be built into systemd!
>
>
>
> --
> So many immigrant groups have swept through our town
> that Brooklyn, like Atlantis, reaches mythological
> proportions in the mind of the world - RI Safir 1998
> http://www.mrbrklyn.com
> DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
>
> http://www.nylxs.com - Leadership Development in Free Software
> http://www.brooklyn-living.com
>
> Being so tracked is for FARM ANIMALS and extermination camps,
> but incompatible with living as a free human being. -RI Safir 2013
>
> _______________________________________________
> Kernelnewbies mailing list
> Kernelnewbies@kernelnewbies.org
> https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>


-- 
*Best Regards,*


*Mr. Irfan Ullah*
PhD Candidate
Data and Knowledge Engineering(DKE) Lab
Department of Computer Science and Engineering
Kyung Hee University, South Korea.
 +82-010-591-51651 <+82%2010-3877-8867>
  sahibzada.iu@gmail.com
 sahibzada_irfanullah

[-- Attachment #1.2: Type: text/html, Size: 4311 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Irfan Ullah (울라 이르판)]

[-- Attachment #1.1: Type: text/plain, Size: 3647 bytes --]

Also, I have one question, here, in this link
<https://stackoverflow.com/questions/35876323/python-netlink-multicast-communication-in-kernels-above-4>,
C is used in the kernel space while Python in the user space. Python
program in the user space successfully catches the char[] data, although it
has some weird characters which I try to remove using split() function. how
it can it be possible to share any type of data structure (e.g., structure,
array, etc.) between  kernel space C program and user space Python program
in two way communication.
Thanks.

Furthermore, @ Valdis Klētnieks,Thank you very much for your useful
comments about the performance. And I know that Python is slow but it is
machine learning rich library, therefore, after finalizing the method and
machine learning model either we will 1) transfer our ready-made model to
the kernel space from user space, or 2) we will develop our own library to
utilize machine learning in the kernel space in some way.

@All,* There is one thing I want to share, although it is not too relevant
but worth to share,*  that very limited number of *easy-to-use-&-understand*
tools and libraries available to welcome  and facilitate the
newbies/freshmen in the kernel development as compare to other development
environments.

On Thu, Oct 10, 2019 at 11:10 AM Irfan Ullah (울라 이르판) <irfan@dke.khu.ac.kr>
wrote:

> Thank you  for the responses.
> It is not my assignment. Actually, we have initiated a project based on
> the idea "incorporating artificial intelligence in the linux kernel to
> increase its performance". The basic aim of the project to increase the
> operating system's performance utilizing software based artificial
> intelligence techniques without using any type of hardware, and then we
> will  test our technique on various hardwares, i.e., classic HDD,SSD, NUMA
> etc. to observe/compare their performances. We took a start from
> prefetching using machine learning.....:)
>
> On Thu, Oct 10, 2019 at 9:26 AM Ruben Safir <ruben@mrbrklyn.com> wrote:
>
>> On 10/9/19 3:08 PM, Valdis Klētnieks wrote:
>> > Ah, academia - where novelty of an idea is sufficient to get published,
>> and considerations
>> > of whether it's a *useful* idea are totally disregarded.
>>
>>
>> or better, it will be built into systemd!
>>
>>
>>
>> --
>> So many immigrant groups have swept through our town
>> that Brooklyn, like Atlantis, reaches mythological
>> proportions in the mind of the world - RI Safir 1998
>> http://www.mrbrklyn.com
>> DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
>>
>> http://www.nylxs.com - Leadership Development in Free Software
>> http://www.brooklyn-living.com
>>
>> Being so tracked is for FARM ANIMALS and extermination camps,
>> but incompatible with living as a free human being. -RI Safir 2013
>>
>> _______________________________________________
>> Kernelnewbies mailing list
>> Kernelnewbies@kernelnewbies.org
>> https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>>
>
>
> --
> *Best Regards,*
>
>
> *Mr. Irfan Ullah*
> PhD Candidate
> Data and Knowledge Engineering(DKE) Lab
> Department of Computer Science and Engineering
> Kyung Hee University, South Korea.
>  +82-010-591-51651 <+82%2010-3877-8867>
>   sahibzada.iu@gmail.com
>  sahibzada_irfanullah
>


-- 
*Best Regards,*


*Mr. Irfan Ullah*
PhD Candidate
Data and Knowledge Engineering(DKE) Lab
Department of Computer Science and Engineering
Kyung Hee University, South Korea.
 +82-010-591-51651 <+82%2010-3877-8867>
  sahibzada.iu@gmail.com
 sahibzada_irfanullah

[-- Attachment #1.2: Type: text/html, Size: 8060 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Valdis Klētnieks]

[-- Attachment #1.1: Type: text/plain, Size: 531 bytes --]

On Thu, 10 Oct 2019 11:48:11 +0900, Irfan Ullah said:

> it can it be possible to share any type of data structure (e.g., structure,
> array, etc.) between  kernel space C program and user space Python program
> in two way communication.

Python's split() is probably the wrong tool here. You probably are looking for
something like this:

https://pymotw.com/2/struct/ - the guys at Python Module Of The Week have you covered.

And a more detailed write-up:
http://archive.oreilly.com/oreillyschool/courses/Python3/Python3-08.html

[-- Attachment #1.2: Type: application/pgp-signature, Size: 832 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Kernel development tools (was Re: Software Prefetching using Machine learning)

[Valdis Klētnieks]

[-- Attachment #1.1: Type: text/plain, Size: 816 bytes --]

On Thu, 10 Oct 2019 11:48:11 +0900, Irfan Ullah said:
> @All,* There is one thing I want to share, although it is not too relevant
> but worth to share,*  that very limited number of *easy-to-use-&-understand*
> tools and libraries available to welcome  and facilitate the
> newbies/freshmen in the kernel development as compare to other development
> environments.

Well... for better or worse, the Linux kernel is an environment where
programmers are expected to have a fairly good grasp on programming and
software development already, and can figure most things out on their own.

Having said that, if you have specific suggestions of tools and libraries that
would make a difference, feel free to state what you think is missing - there's
a good chance that it actually exists but you didn't know about it....


[-- Attachment #1.2: Type: application/pgp-signature, Size: 832 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Kernel development tools (was Re: Software Prefetching using Machine learning)

[Irfan Ullah (울라 이르판)]

[-- Attachment #1.1: Type: text/plain, Size: 2070 bytes --]

Thank you.
You are absolutely right. As a freshman in the kernel development, and
having experience in high level languages, things look complicated :(.
Can you please suggest me what is the efficient and easy way to exchange
data between kernel space and user space. I want the way in which the
kernel should initiate the communication; the kernel daemon first sends the
data to the user space daemon, and the user space daemon (waiting and
listening to the kernel space daemon) receives and processes the data, and
then sends feedback. There are many tools i.e., netlink
(connectionless, asynchronous), ioctl, and /proc available.
Which tool,  and library you suggest for performing the task? and How it
could be done?
I would be grateful if you could provide me with some links/examples/blogs.
Thanks again :).

On Thu, Oct 10, 2019 at 2:51 PM Valdis Klētnieks <valdis.kletnieks@vt.edu>
wrote:

> On Thu, 10 Oct 2019 11:48:11 +0900, Irfan Ullah said:
> > @All,* There is one thing I want to share, although it is not too
> relevant
> > but worth to share,*  that very limited number of
> *easy-to-use-&-understand*
> > tools and libraries available to welcome  and facilitate the
> > newbies/freshmen in the kernel development as compare to other
> development
> > environments.
>
> Well... for better or worse, the Linux kernel is an environment where
> programmers are expected to have a fairly good grasp on programming and
> software development already, and can figure most things out on their own.
>
> Having said that, if you have specific suggestions of tools and libraries
> that
> would make a difference, feel free to state what you think is missing -
> there's
> a good chance that it actually exists but you didn't know about it....
>
>

-- 
*Best Regards,*


*Mr. Irfan Ullah*
PhD Candidate
Data and Knowledge Engineering(DKE) Lab
Department of Computer Science and Engineering
Kyung Hee University, South Korea.
 +82-010-591-51651 <+82%2010-3877-8867>
  sahibzada.iu@gmail.com
 sahibzada_irfanullah

[-- Attachment #1.2: Type: text/html, Size: 4105 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Kernel development tools (was Re: Software Prefetching using Machine learning)

[Greg KH]

On Thu, Oct 10, 2019 at 03:21:46PM +0900, Irfan Ullah (울라 이르판) wrote:
> Thank you.
> You are absolutely right. As a freshman in the kernel development, and
> having experience in high level languages, things look complicated :(.
> Can you please suggest me what is the efficient and easy way to exchange
> data between kernel space and user space. I want the way in which the
> kernel should initiate the communication; the kernel daemon first sends the
> data to the user space daemon, and the user space daemon (waiting and
> listening to the kernel space daemon) receives and processes the data, and
> then sends feedback. There are many tools i.e., netlink
> (connectionless, asynchronous), ioctl, and /proc available.
> Which tool,  and library you suggest for performing the task? and How it
> could be done?
> I would be grateful if you could provide me with some links/examples/blogs.

I think you already have the list above (netlink, ioctl, proc), so just
start with those and see how it goes.

Note, the kernel can not "send userspace something and wait for it to
send a response" and expect to keep on working, as the kernel can never
wait for userspace to do something as that would cause it to stop.

Best of luck!

greg k-h

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Software Prefetching using Machine learning

[Rik van Riel]

[-- Attachment #1.1: Type: text/plain, Size: 1614 bytes --]

On Thu, 2019-10-10 at 11:10 +0900, Irfan Ullah (울라 이르판) wrote:
> Thank you  for the responses.
> It is not my assignment. Actually, we have initiated a project based
> on the idea "incorporating artificial intelligence in the linux
> kernel to increase its performance". 

That is an interesting idea, but it is worth keeping in
mind that most "kernel performance" is not about how well
the kernel does something, but about how quickly the kernel
lets userland programs do things.

For example, I have done a lot of work on the scheduler
code recently, and the most common thing I see (whenever
I try something wrong) is for total CPU use in the system
to go up. However, the increase in CPU time used is often
in user space, and not in the kernel.

For example, trying out a bad idea might result in 0.2%
more CPU time spent in the kernel, but 2% more CPU time
spent in user space, due to seeing a larger number of
cache misses from user space programs.

When things are done right, enabling a certain kernel
feature might result in some overhead (say 0.3%), which
is almost entirely caused by cache line misses, resulting
in a total system overhead of twice that (0.6%), because
every cache miss in my code results in something else
getting evicted from the cache, and somebody else incurring
a cache miss as well.

In short, if you want to use machine learning to improve
kernel performance, you need to figure out a way to do
that without causing cache misses in any really hot path.

That puts a serious constraint on what you can do.

-- 
All Rights Reversed.

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies