I am not categorically opposed to the idea of having self-optimizing
data structures. I am a bit skeptical about being able to find right
heuristics for such optimizations, and making them portable is another
big issue.
At this point, it looks like it can be a future step of a GSoC project.
Remember, at the end students should produce something that is
contributed upstream. And I have a feeling that such an automatic
optimization idea would take a lot of time to perfect, which makes it a
bit adventurous idea to me.
Engin
On 03/13/2017 05:23 PM, Raghav Arora wrote:
> Dear Engin,
>
> I understand the network overhead and we can make that into an explicit
> command, and not the default functionality of the structure. Also we can
> call it something other than lists, for example OpList (short for
> Optimizable List). However, the user will not have any power to control
> which data structure the OpList gets converted to, i.e. It depends on the
> usage characteristics of that specific function. My aim here is to minimize
> complexity during normal usage with a little storage overhead, storing
> usage trends as metadata in the form of instance variables.
>
> The developer or user can also call a status function which suggests wether
> running the optimization function is advisable or not.
>
> So what I am saying can be understood like this (using code representation
> not actual code)
>
> class OpList
> {
> int w1, w2, w3, x1, x2, y, z1, z2 // variables which store usage
> trends (ultimately forming parameters for a deterministic equation)
>
> void optimize()
> {
> // some computation based on w1, w2, w3, x1, x2, y, z1, z2
> }
> void status()
> {
> if ( some condition )
> print ( " Optimization necessary " )
> else if (some condition )
> print ( " Optimization suggested but not necessary ")
> else
> print ( " Optimization not required " )
> }
> }
>
>
> Please do let me know if I am thinking in the right direction or even if
> it's an unnecessary addition.
>
> Thanks and Regards,
> Raghav Arora
>
> On Mon, Mar 13, 2017 at 9:48 PM, Engin Kayraklioglu <[email protected]>
> wrote:
>
>> Hello,
>>
>> First of all we have a rather simple, non-distributed, non-parallel-safe
>> list structure in Chapel:
>>
>> http://chapel.cray.com/docs/latest/modules/standard/List.html
>>
>> Structures you suggested seems a good list for common structures.
>>
>> As for optimizations: I like the general idea. I can imagine
>> asynchronous tasks coming to help create some redundancy/variation in
>> the way the data is stored. But at the same time, I'd be very careful
>> since such reorganizations could create a lot of communication over the
>> network. Especially if we are thinking about doing such operations
>> without any instructions from the programmer, it can create unexpected
>> performance overheads.
>>
>> Engin
>>
>> On 03/13/2017 04:29 PM, Raghav Arora wrote:
>>> Hello Engin and Param,
>>>
>>> As Engin already knows, I have shown interest in developing distributed
>>> data structures.
>>>
>>> I think we should start with basic data structures like:
>>>
>>> 1. Stack
>>> 2. Queue
>>> a. Basic Queue
>>> b. Priority Queue
>>> c. Dequeue
>>> d. Circular Queue
>>> 4. Sets
>>>
>>>
>>> Then we should implement linked lists - both single and double linked
>>>
>>> Then we can use these structures further to implement Trees and Graphs.
>>>
>>> What are your thoughts? Also, in case an implementation for any of these
>>> already exists, please forgive me as I am new to Chapel.
>>>
>>> And I tried to think over what Engin said about different
>>> implementations for different workloads, and I think we can have a
>>> generic data type called List (or maybe anything else), which implements
>>> functionality from different data structures depending on the conditions
>>> during their initialization. Furthermore, we can also have an optimize
>>> function which interchanges implementation between data structures by
>>> converting the way the data is stored. For example, Let's say I am doing
>>> a lot of search operations on an array. A better data structure to carry
>>> out search operations is a binary search tree. We can easily detect
>>> operations we do on these lists and increment / decrement certain
>>> parameters in a function whose output decides which data structure to
>>> continue with. Again, what are your thoughts?
>>>
>>>
>>> Best,
>>> Raghav
>>>
>>> On Mon, Mar 13, 2017 at 7:18 PM, Engin Kayraklioglu <[email protected]
>>> <mailto:[email protected]>> wrote:
>>>
>>> Hey Param,
>>>
>>> I think the basic ones you listed are the most important ones.
>>>
>>> (If you want to consider hashtables, you should be aware of
>> associative
>>> domains/arrays in Chapel:
>>> http://chapel.cray.com/docs/master/primers/primers/associative.html
>>> <http://chapel.cray.com/docs/master/primers/primers/associative.html
>>> )
>>>
>>> >From then on, if you want to expand, you can do it by adding more
>> depth
>>> or breadth to it. ie, you can propose to have small set of
>>> performant/scalable distributed data structures (maybe by
>>> proposing/investigating different queue implementations that can
>> perform
>>> differently under different workloads), or a bigger set of structures
>>> that covers wider variety of functionality that you think would be
>>> useful for Chapel.
>>>
>>> It depends on what you are able/want to do in the given time frame.
>>>
>>> Engin
>>>
>>> On 03/11/2017 11:35 AM, Param Hanji wrote:
>>> > Hi Engin,
>>> >
>>> > I tried looking for existing distributed data structure libraries,
>> and
>>> > came across Hazelcast
>>> >
>>> <http://docs.hazelcast.org/docs/3.5/manual/html/
>> distributed-data-structures.html
>>> <http://docs.hazelcast.org/docs/3.5/manual/html/
>> distributed-data-structures.html>>,
>>> Multipol
>>> >
>>> <http://digitalassets.lib.berkeley.edu/techreports/ucb/
>> text/CSD-95-879.pdf
>>> <http://digitalassets.lib.berkeley.edu/techreports/ucb/
>> text/CSD-95-879.pdf>>
>>> and Ignite
>>> > <https://ignite.apache.org/features/datastructures.html
>>> <https://ignite.apache.org/features/datastructures.html>>, among
>> others.
>>> > I noticed that these libraries have implementations for different
>> data
>>> > structures and need insights about which data structures will be
>> useful
>>> > for Chapel users. I believe you or someone else who has used Chapel
>>> > extensively, will be in a better position to identify data
>> structures
>>> > that are used often.
>>> >
>>> > Once we have figured out which structures are required, I can
>> perhaps
>>> > think about and propose implementations for them. I'm sure some
>> basic
>>> > ones like stack, queue, hashmap, set, etc. will be useful for most
>>> > users. What others am I expected to include in the library?
>>> >
>>> > On Mon, Mar 6, 2017 at 10:57 PM Engin Kayraklioglu <
>> [email protected] <mailto:[email protected]>
>>> > <mailto:[email protected] <mailto:[email protected]>>> wrote:
>>> >
>>> > Hey Param,
>>> >
>>> > As far as distributed data structures, there is nothing
>>> special that I
>>> > can refer you to. I suggest searching what kind of distributed
>>> data
>>> > structure libraries out there (in other languages), and what is
>>> > suitable/useful for Chapel.
>>> >
>>> > On a slightly related note:
>>> >
>>> > http://chapel.cray.com/docs/latest/modules/layoutdist.html
>>> <http://chapel.cray.com/docs/latest/modules/layoutdist.html>
>>> >
>>> > Standard Distributions in this link discusses how Chapel
>>> distributes
>>> > arrays over multiple nodes in a system.
>>> >
>>> > Engin
>>> >
>>> > On 03/04/2017 07:59 AM, Param Hanji wrote:
>>> > > Hi,
>>> > >
>>> > > I am Param Hanji, an undergrad student from India, studying
>>> at the
>>> > > National Institute of Technology, Karnataka. I came across
>>> Chapel
>>> > on the
>>> > > GSoC '17 Organisations page and decided to give it a shot.
>>> > >
>>> > > I've downloaded Chapel on my laptop using Homebrew and
>>> played around a
>>> > > little to get used to the new language and am really liking
>> the
>>> > > experience. I followed some the tutorials mentioned on the
>>> website.
>>> > > After working with frameworks like OpenCL, CUDA, OpenMP
>>> etc., using
>>> > > Chapel for parallelising code seems so simplistic!
>>> > >
>>> > > I'd love to contribute to the existing codebase and am
>>> interested
>>> > in the
>>> > > Distributed Data Structures project. This will require
>>> creating an
>>> > > entirely new module right? Are there any resources on
>>> distributed data
>>> > > structures that I can refer to?
>>> > >
>>> > > Cheers,
>>> > > Param Hanji
>>> > >
>>> > >
>>> > >
>>> > >
>>> > >
>>> >
>>> ------------------------------------------------------------
>> ------------------
>>> > > Check out the vibrant tech community on one of the world's
>> most
>>> > > engaging tech sites, SlashDot.org! http://sdm.link/slashdot
>>> > >
>>> > >
>>> > >
>>> > > _______________________________________________
>>> > > Chapel-developers mailing list
>>> > > [email protected]
>>> <mailto:[email protected]>
>>> > <mailto:[email protected]
>>> <mailto:[email protected]>>
>>> > > https://lists.sourceforge.net/lists/listinfo/chapel-
>> developers
>>> <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
>>> > >
>>> >
>>> > ------------------------------------------------------------
>> ------------------
>>> > Announcing the Oxford Dictionaries API! The API offers
>> world-renowned
>>> > dictionary content that is easy and intuitive to access. Sign
>> up for an
>>> > account today to start using our lexical data to power your
>> apps and
>>> > projects. Get started today and enter our developer
>> competition.
>>> > http://sdm.link/oxford
>>> > _______________________________________________
>>> > Chapel-developers mailing list
>>> > [email protected]
>>> <mailto:[email protected]>
>>> > <mailto:[email protected]
>>> <mailto:[email protected]>>
>>> > https://lists.sourceforge.net/lists/listinfo/chapel-developers
>>> <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
>>> >
>>>
>>> ------------------------------------------------------------
>> ------------------
>>> Check out the vibrant tech community on one of the world's most
>>> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>>> _______________________________________________
>>> Chapel-developers mailing list
>>> [email protected]
>>> <mailto:[email protected]>
>>> https://lists.sourceforge.net/lists/listinfo/chapel-developers
>>> <https://lists.sourceforge.net/lists/listinfo/chapel-developers>
>>>
>>>
>>
>
>
>
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>
>
>
> _______________________________________________
> Chapel-developers mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/chapel-developers
>
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Chapel-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/chapel-developers
